binary-tree-traversal.md

二叉树遍历

遍历介绍

对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。

四种基本的遍历思想为：

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点
• 层次遍历：按层次遍历

前三种遍历使用递归实现比较方便，层次遍历借助栈结构实现方便

举例 1

         a
        /  \
       b    c
     /   \  
    d     f 
     \   /
      e  g

 
- 前序遍历：a b d e f g c 

- 中序遍历：d e b g f a c

- 后序遍历：e d g f b c a 

- 层次遍历：a b c d f e g 

举例 2

         A
       /   \
      B     E
       \     \
        C      F
       /     /
      D     G
           / \       
          H   K
      
- 前序，根左右：A B C D E F G H K
- 中序，左根右：B D C A E H G K F
- 后序，左右根，D C B H K G F E A
- 层次遍历：   A B E C F D G H K

从序列构造二叉树

从前序与中序遍历序列构造二叉树

- 前序遍历：a b d e f g c 
- 中序遍历：d e b g f a c

前序第一个节点就是跟节点 a
在中序中查找，a 左边的就在左子树 [d e b g f] 的中序有 5 个元素，a 右边的就在右子树 [c] 中序有 1 个元素 所以在前序的 a 后面的 5 个元素 [b d e f g]，是左子树的前序序列，剩下的[c] 为右子树的前序序列 同样的情况递归下去就行 以前序 = [b d e f g]，中序 = [d e b g f] 来说，b 为跟节点 ，[d e] 为左中序， [d e]也为左前序，[g f] 为右中序，[f g]为右前序

从中序与后序遍历序列构造二叉树

参考

https://www.cnblogs.com/llguanli/p/7363657.html