一、二叉树的先序遍历（根左右NLR）

• 如下图，先序遍历结果为：A B D E C F G
  
• 如下图，先序遍历结果为：A B D G E C F
  

二、二叉树的中序遍历（根左右LNR）

• 如下图，中序遍历结果为：D B E A F C G
  
• 如下图，中序遍历结果为：D G B E A F C
  

三、二叉树的后序遍历（左右根LRN）

• 如下图，后序遍历结果为：D E B F G C A
  
• 如下图，后序遍历结果为：G D E B F C A
  

四、二叉树的层次遍历

树的层次遍历算法思想:

• （1）初始化一个辅助队列
• （2）根结点入队
• （3）若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾(如果有的话)
• （4）重复（3）直至队列为空

五、由遍历构造二叉树

5.1 不同二叉树的先序遍历

• 一个前序遍历序列可能对应多种二叉树形态

• 一个中序遍历序列可能对应多种二叉树形态
  
• 一个后序遍历序列可能对应多种二叉树形态
  
• 一个层序遍历序列可能对应多种二叉树形态
  

5.2 由遍历构造二叉树

• 结论:若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树

5.3 前序+中序遍历构造二叉树

构建过程：

• （1）由前序遍历得到根节点，确定A的位置
• （2）再由中序遍历确定左右孩子，确定BDC和E的位置
• （3）采用（1）和（2）的过程，递归构建二叉树

5.4 后序+中序遍历构造二叉树

构建过程：

• （1）由后序遍历得到根节点，确定D的位置
• （2）再由中序遍历确定左右孩子，确定EAF和HCBGI的位置
• （3）采用（1）和（2）的过程，递归构建二叉树

5.5 层序+中序遍历构造二叉树

构建过程：

• （1）由层序遍历得到根节点，确定D的位置
• （2）再由中序遍历确定左右孩子，确定EAF和HCBGI的位置
• （3）采用（1）和（2）的过程，递归构建二叉树
  
  

5.5 总结

• 重点: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点