二叉树专题

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

四种主要的遍历思想为：

1. 前序遍历：根结点 ---> 左子树 ---> 右子树（根左右）

2. 中序遍历：左子树---> 根结点 ---> 右子树（左根右）

3. 后序遍历：左子树 ---> 右子树 ---> 根结点（左右根）

4. 层次遍历：只需按层次遍历即可

前序遍历: 56 22 10 30 81 77 92

中序遍历: 10 22 30 56 77 81 92

后序遍历: 10 30 22 77 92 81 56

这里发现了一些规律：

1. 前序遍历，因为是根左右，所以最后一个一定是最大的； 第一个一定是root节点；

2. 中序遍历，在查找二叉树中，一定是从小到大的顺序； 根节点56左边(10/22/30)的一定是左子树的，右边的(77/81/92)一定是右子树的。

3. 后序遍历，根节点一定在最后

二叉树的例子

var tree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    },
    right: {
      value: 6
    }
  }
}

参考资料

http://www.conardli.top/docs/dataStructure/%E4%BA%8C%E5%8F%89%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%91.html