js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

树的简介

栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。

树型结构

树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。

树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：

有且仅有一个特定的称为根（Root）的结点；
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3,...Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。

例如，（a）是只有一个根结点的树；（b）是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子树，且本身也是一棵树。

树的结点包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数称为结点的度（Degree）。例如，（b）中A的度为3，C的度为1，F的度为0。度为0的结点称为叶子（Leaf）或者终端结点。度不为0的结点称为非终端结点或分支结点。

树的度是树内各结点的度的最大值。（b）的树的度为3。结点的子树的根称为该结点的孩子（Child）。相应的，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

结点的层次（Level）从根开始定义起，根为第一层，跟的孩子为第二层。若某结点在第层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。例如，结点G与E，F,H,I,J互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。（b）的树的深度为4。

求树的深度：看这篇：https://www.jianshu.com/p/9fc3d66e5c87

如果将树中结点的各子树看成从左至右是有次序的（即不能交换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林（Forest）是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

二叉树

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分（其次序不能任意颠倒。）

二叉树的性质：

在二叉树的第 i 层上至多有 $2^{i-1}$ 个结点(i>=1)。
深度为k的二叉树至多有 $2^k - 1$ 个结点，(k>=1)。
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1;
一棵深度为k且有 $2^k$ - 1个结点的二叉树称为满二叉树。
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

完全二叉树的两个特性：

具有n个结点的完全二叉树的深度为 $Math.floor(log_2 n) + 1$ ;
如果对一棵有n个结点的完全二叉树（其深度为 $Math.floor(log_2 n) + 1$ ）的结点按层序编号（从第1层到第 $Math.floor(log_2 n) + 1$ ，每层从左到右），则对任一结点（1<=i<=n）有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲parent(i)是结点Math.floor(i/2)。
如果2i > n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LChild(i)是结点2i.
如果2i + 1 > n，则结点i无右孩子；否则其右孩子RChild(i)是结点2i + 1;

二叉树

完全二叉树

二叉树的存储结构

顺序存储结构

用一组连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。“0”表示不存在此结点。这种顺序存储结构仅适用于完全二叉树。因为，在最坏情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2的n次方-1的一维数组。

顺序：[1, 2, 3, 4, 5, , 6, , , 7]

链式存储结构

二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左右指针域。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。在含有n个结点的二叉链表中有n+1个空链域，我们可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构---线索链表。

链式：{ data, left, right}

二叉树的遍历

遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。

二叉树有深度遍历和广度遍历，深度遍历有前序、中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等；中序遍历可以实现表达式树，在编译器底层很有用；后序遍历可以用来实现计算目录内的文件及其信息等。

二叉树是非常重要的数据结构，其中二叉树的遍历要使用到栈和队列还有递归等，很多其它数据结构也都是基于二叉树的基础演变而来的。熟练使用二叉树在很多时候可以提升程序的运行效率，减少代码量，使程序更易读。

二叉树不仅是一种数据结构，也是一种编程思想。学好二叉树是程序员进阶的一个必然进程。

前序遍历：访问根–>遍历左子树–>遍历右子树;
中序遍历：遍历左子树–>访问根–>遍历右子树;
后序遍历：遍历左子树–>遍历右子树–>访问根;
广度遍历：按照层次一层层遍历;

例如(a+b*c)-d/e，该表达式用二叉树表示如图：

(a+b*c)-d/e

对该二叉树进行深度和广度遍历为：

*前序遍历：- + a * b c / d e
中序遍历：a + b * c - d / e
后序遍历：a b c + d e / -
广度遍历：- + / a * d e b c

1. js中的二叉树

上述二叉树(a+b*c)-d/e在js中可以用对象的形式表示出来：

var tree = {
    value: "-",
    left: {
        value: '+',
        left: {
            value: 'a',
        },
        right: {
            value: '*',
            left: {
                value: 'b',
            },
            right: {
                value: 'c',
            }
        }
    },
    right: {
        value: '/',
        left: {
            value: 'd',
        },
        right: {
            value: 'e',
        }
    }
}

2. js中二叉树的深度遍历

深度遍历也可称为深度优先遍历（Depth-First Search，DFS），因为它总是优先往深处访问。

先序遍历

递归遍历

let result = [];
let dfs = function (node) {
    if(node) {
        result.push(node.value);
        dfs(node.left);
        dfs(node.right);
    }
}

dfs(tree);
console.log(result); 
// ["-", "+", "a", "*", "b", "c", "/", "d", "e"]

先序递归遍历思路：

先遍历根结点，将值存入数组，然后递归遍历：先左结点，将值存入数组，继续向下遍历；直到（二叉树为空）子树为空，则遍历结束；
然后再回溯遍历右结点，将值存入数组，这样递归循环，直到（二叉树为空）子树为空，则遍历结束。

非递归遍历（利用栈：将遍历到的结点都依次存入栈中，拿结果时从栈中访问）

let dfs = function (nodes) {
    let result = [];
    let stack = [];
    stack.push(nodes);
    while(stack.length) { // 等同于 while(stack.length !== 0) 直到栈中的数据为空
        let node = stack.pop(); // 取的是栈中最后一个j
        result.push(node.value);
        if(node.right) stack.push(node.right); // 先压入右子树
        if(node.left) stack.push(node.left); // 后压入左子树
    }
    return result;
}
dfs(tree);

先序非递归遍历思路：

初始化一个栈，将根节点压入栈中；
当栈为非空时，循环执行步骤3到4，否则执行结束；
从队列取得一个结点（取的是栈中最后一个结点），将该值放入结果数组；
若该结点的右子树为非空，则将该结点的右子树入栈，若该结点的左子树为非空，则将该结点的左子树入栈；（注意：先将右结点压入栈中，后压入左结点，从栈中取得时候是取最后一个入栈的结点，而先序遍历要先遍历左子树，后遍历右子树）

中序遍历

递归遍历

let result = [];
let dfs = function (node) {
     if(node) {
        dfs(node.left);
        result.push(node.value); // 直到该结点无左子树 将该结点存入结果数组 接下来并开始遍历右子树
        dfs(node.right);
    }
}

dfs(tree);
console.log(result);
//  ["a", "+", "b", "*", "c", "-", "d", "/", "e"]

中序递归遍历的思路：

先递归遍历左子树，从最后一个左子树开始存入数组，然后回溯遍历双亲结点，再是右子树，这样递归循环。

非递归遍历

function dfs(node) {
    let result = [];
    let stack = [];
    while(stack.length || node) { // 是 || 不是 &&
        if(node) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            result.push(node.value);
            //node.right && stack.push(node.right);
            node = node.right; // 如果没有右子树 会再次向栈中取一个结点即双亲结点
        }
    }
    return result;
}

dfs(tree);
// ["a", "+", "b", "*", "c", "-", "d", "/", "e"]

一种利用回溯法思想的代码：
看这里：https://zhuanlan.zhihu.com/p/27307626 但是他的代码有些问题。。。

非递归遍历的思路：

将当前结点压入栈，然后将左子树当做当前结点，如果当前结点为空，将双亲结点取出来，将值保存进数组，然后将右子树当做当前结点，进行循环。

后序遍历

递归遍历

result = [];
function dfs(node) {
    if(node) {
        dfs(node.left);
        dfs(node.right);
        result.push(node.value);
    }
}
dfs(tree);
console.log(result);
// ["a", "b", "c", "*", "+", "d", "e", "/", "-"]

写到这，深深的被递归折服。。。。服

先走左子树，当左子树没有孩子结点时，将此结点的值放入数组中，然后回溯遍历双亲结点的右结点，递归遍历。

非递归遍历

(含大量注释代码的)

function dfs(node) {
    let result = [];
    let stack = [];
    stack.push(node);
    while(stack.length) {
        // 不能用node.touched !== 'left' 标记‘left’做判断，
        // 因为回溯到该结点时，遍历右子树已经完成，该结点标记被更改为‘right’ 若用标记‘left’判断该if语句会一直生效导致死循环
        if(node.left && !node.touched) { // 不要写成if(node.left && node.touched !== 'left')
            // 遍历结点左子树时，对该结点做 ‘left’标记；为了子结点回溯到该（双亲）结点时，便不再访问左子树
            node.touched = 'left';
            node = node.left;
            stack.push(node);
            continue;
        }
        if(node.right && node.touched !== 'right') { // 右子树同上
            node.touched = 'right';
            node = node.right;
            stack.push(node);
            continue;
        }
        node = stack.pop(); // 该结点无左右子树时，从栈中取出一个结点，访问(并清理标记)
        node.touched && delete node.touched; // 可以不清理不影响结果 只是第二次对同一颗树再执行该后序遍历方法时，结果就会出错啦因为你对这棵树做的标记还留在这棵树上
        result.push(node.value);
        node = stack.length ? stack[stack.length - 1] : null;
        //node = stack.pop(); 这时当前结点不再从栈中取（弹出），而是不改变栈数据直接访问栈中最后一个结点
        //如果这时当前结点去栈中取（弹出）会导致回溯时当该结点左右子树都被标记过时 当前结点又变成从栈中取会漏掉对结点的访问（存入结果数组中）
    }
    return result; // 返回值
}

dfs(tree);

后序遍历非递归遍历思路：先把根结点和左树推入栈，然后取出左树，再推入右树，取出，最后取根结点。

步骤：

初始化一个栈，将根节点压入栈中，并标记为当前节点(node)；
当栈为非空时，执行步骤3，否则执行结束；
如果当前节点(node)有左子树且没有被 touched，则执行4；如果当前结点有右子树，被 touched left 但没有被 touched right 则执行5 否则执行6；
对当前节点(node)标记 touched left，将当前节点的左子树赋值给当前节点(node=node.left) 并将当前节点(node)压入栈中，回到3；
对当前节点(node)标记 touched right，将当前节点的右子树赋值给当前节点(node=node.right) 并将当前节点(node)压入栈中，回到3；
清理当前节点(node)的 touched 标记，弹出栈中的一个节点并访问，然后再将栈顶节点标记为当前节点(item)，回到3；

3. js中二叉树的广度遍历

广度优先遍历二叉树(层序遍历)是用队列来实现的，广度遍历是从二叉树的根结点开始，自上而下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

递归遍历

let result = [];
let stack = [tree]; // 先将要遍历的树压入栈
let count = 0; // 用来记录执行到第一层
let bfs = function () {
    let node = stack[count];
    if(node) {
        result.push(node.value);
        if(node.left) stack.push(node.left);
        if(node.right) stack.push(node.right);
        count++;
        bfs();
    }
}
dfc();
console.log(result);
//  ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

非递归算法

function bfs(node) {
    let result = [];
    let queue = [];
    queue.push(node);
    let pointer = 0;
    while(pointer < queue.length) {
        let node = queue[pointer++]; // // 这里不使用 shift 方法（复杂度高），用一个指针代替
        result.push(node.value);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result;
}

bfs(tree);
// ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

另外一种比较消耗性能的方法：不额外定义一个指针变量 pointer，使用数组的shift()方法，每次改变 queue 的数据（入栈、出栈），来读取数据，直到栈 queue 中数据为空，执行结束。（频繁的改变数组，因为数组是引用类型，要改变它，要新开辟一个地址，所以比较消耗空间）

function bfs (node) {
    let result = [];
    let queue = [];
    queue.push(node);
    while(queue.length) {
        node = queue.shift();
        result.push(node.value); // 不要忘记访问
        // console.log(node.value);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result;
}
bfs(tree);
//  ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

References

二叉树与JavaScript
JavaScript与简单算法
 javascript实现数据结构：树和二叉树,二叉树的遍历和基本操作
 图的基本算法（BFS和DFS）
搜索思想——DFS & BFS（基础基础篇）