课程名称: JavaScript版数据结构与算法
课程章节:第8章 数据结构之“树”
课程讲师: lewis
课程内容:前端JS的算法基础
课程介绍:
8-1 树简介
8-2 深度与广度优先遍历
8-3 二叉树的先中后序遍历
8-4 二叉树的先中后序遍历(非递归版)
8-5 LeetCode:104. 二叉树的最大深度
8-6 LeetCode:111. 二叉树的最小深度
8-7 LeetCode:102. 二叉树的层序遍历
8-8 LeetCode:94. 二叉树的中序遍历
8-9 LeetCode:112. 路径总和
8-10 前端与树:遍历 JSON 的所有节点值
不管是深度优先遍历还是广度优先遍历,都可以用递归算法或者非递归算法来实现,一般情况下递归算法比较容易实现,并且看起来直观,但是由于涉及到层层的函数栈调用,性能不高,而非递归算法有着比较好的性能。文章下面对深度优先遍历和广度优先遍历都做了算法描述和递归/非递归实现
首先我们定义这样的一个二叉树结构:
var nodes = { node: 6, left: { node: 5, left: { node: 4 }, right: { node: 3 } }, right: { node: 2, right: { node: 1 } } }
下面所有的代码都将对上述数据结构进行遍历。
递归算法
若二叉树为空,则算法结束,否则:
访问根结点;
前序遍历根结点的左子树;
前序遍历根结点的右子树。
var result = [] var dfs = function(nodes) { if(nodes.node) { result.push(nodes.node) nodes.left && dfs(nodes.left) nodes.right && dfs(nodes.right) } } dfs(nodes) console.log(result) // [6, 5, 4, 3, 2, 1]
非递归算法
初始化一个栈,将根节点压入栈中;
当栈为非空时,循环执行步骤3到4,否则执行结束;
出队列取得一个结点,访问该结点;
若该结点的右子树为非空,则将该结点的右子树入栈,若该结点的左子树为非空,则将该结点的左子树入栈;
var dfs = function(nodes) { var result = [] var stack = [] stack.push(nodes) while (stack.length) { var item = stack.pop() result.push(item.node) item.right && stack.push(item.right) item.left && stack.push(item.left) } return result } console.log(dfs(nodes)) // [6, 5, 4, 3, 2, 1]
递归算法
若二叉树为空,则算法结束;否则:
中序遍历根结点的左子树;
访问根结点;
中序遍历根结点的右子树;
var result = [] var dfs = function(nodes) { if(nodes.node) { nodes.left && dfs(nodes.left) result.push(nodes.node) nodes.right && dfs(nodes.right) } } dfs(nodes) console.log(result) // [4, 5, 3, 6, 2, 1]
非递归算法
初始化一个栈,将根节点压入栈中,并标记为当前节点(item);
当栈为非空时,执行步骤3,否则执行结束;
如果当前节点(item)有左子树且没有被 touched,则执行4,否则执行5;
对当前节点(item)标记 touched,将当前节点的左子树赋值给当前节点(item=item.left) 并将当前节点(item)压入栈中,回到3;
清理当前节点(item)的 touched 标记,取出栈中的一个节点标记为当前节点(item),并访问,若当前节点(item)的右子树为非空,则将该结点的右子树入栈,回到3;
var dfs = function(nodes) { var result = [] var stack = [] var item = nodes stack.push(nodes) while (stack.length) { if(item.left && !item.touched) { item.touched = true item = item.left stack.push(item) continue } item.touched && delete item.touched // 清理标记 item = stack.pop() result.push(item.node) item.right && stack.push(item.right) } return result } console.log(dfs(nodes)) // [4, 5, 3, 6, 2, 1]
递归算法:
若二叉树为空,则算法结束,否则:
后序遍历根结点的左子树;
后序遍历根结点的右子树;
访问根结点。
var result = [] var dfs = function(nodes) { if(nodes.node) { nodes.left && dfs(nodes.left) nodes.right && dfs(nodes.right) result.push(nodes.node) } } dfs(nodes) console.log(result) // [4, 3, 5, 1, 2, 6]
非递归算法:
初始化一个栈,将根节点压入栈中,并标记为当前节点(item);
当栈为非空时,执行步骤3,否则执行结束;
如果当前节点(item)有左子树且没有被 touched,则执行4,如果被 touched left 但没有被 touched right 则执行5 否则执行6;
对当前节点(item)标记 touched left,将当前节点的左子树赋值给当前节点(item=item.left) 并将当前节点(item)压入栈中,回到3;
对当前节点(item)标记 touched right,将当前节点的右子树赋值给当前节点(item=item.right) 并将当前节点(item)压入栈中,回到3;
清理当前节点(item)的 touched 标记,弹出栈中的一个节点并访问,然后再将栈顶节点标记为当前节点(item),回到3;
var dfs = function(nodes) { var result = [] var stack = [] var item = nodes stack.push(nodes) while (stack.length) { if(item.left && !item.touched) { item.touched = 'left' item = item.left stack.push(item) continue } if(item.right && item.touched !== 'right') { item.touched = 'right' item = item.right stack.push(item) continue } var out = stack.pop() out.touched && delete out.touched // 清理标记 result.push(out.node) item = stack.length ? stack[stack.length - 1] : null } return result } console.log(dfs(nodes)) // [4, 3, 5, 1, 2, 6]
广度优先遍历二叉树(层序遍历)是用队列来实现的,从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。步骤:
初始化一个队列,并把根结点入列队;
当队列为非空时,循环执行步骤3到4,否则执行结束;
出队列取得一个结点,访问该结点;
若该结点的左子树为非空,则将该结点的左子树入队列,若该结点的右子树为非空,则将该结点的右子树入队列;
递归算法:
var result = [] var queue = [nodes] var bfs = function(count) { count = count || 0 if(queue[count]) { result.push(queue[count].node) var left = queue[count].left var right = queue[count].right if(left) { queue.push(left) } if(right) { queue.push(right) } bfs(++count) } } bfs() console.log(result) // [6, 5, 2, 4, 3, 1]
非递归算法
var bfs = function(nodes) { var result = [] var queue = [] var pointer = 0 queue.push(nodes) while(pointer < queue.length) { var item = queue[pointer++] // 这里不使用 shift 方法(复杂度高),用一个指针代替 result.push(item.node) console.log(item.node) item.left && queue.push(item.left) item.right && queue.push(item.right) } return result } console.log(bfs(nodes)) // [6, 5, 2, 4, 3, 1]
在实际生产过程中尽量避免递归的调用,应为其时间复杂度,树和图是数据结构中最基础和最重要的组成部分,其经典应用还有红黑树,平衡二叉树等经典问题。