二叉树的遍历

一、先中后遍历（递归）

1、先序遍历：根，左子树，右子树（根在先）

图1：2 7 1 6 5 3 8 9 4；

图2：A B C K D E H F J G

2、中序遍历：　　左子树，根，右子树（根在中）

图1：1 7 5 6 3 2 8 4 9；

图2：B K C A H E D H F G.

3、后序遍历：　　左子树，右子树，根（根在后）

图1：1 5 3 6 7 4 9 8 2；

图2：K C B H E J G F D A

自己再一次写出上面两棵树前序（先序）遍历、中序遍历、后序遍历的结果，然后对照上面的结果，如果出现错误一定要重视，说明还不完全理解遍历的过程。

二、题型

1、题型一：已知其中两种遍历结果，求第三种遍历结果。

2、题型二：统计 $n$ 个不同编号的点可以构造多少棵不同的二叉树？

答：Catalan数= $\frac{C_{2n}^n}{n+1}$。

3、题型三：中缀表达式向前缀和后缀表达式的转化（ 2009提高（同2009普及）选择题6 ）

结论1：已知先序和中序，二叉树是唯一的。

结论2：已知后序和中序，二叉树是唯一的。

结论3：已知先序和后序，二叉树不是唯一的。

例1、已知先序：1 2 4 3 5 7 6， 中序：2 4 1 7 5 3 6，请画出整棵二叉树。

例2、已知后序：4 5 2 6 7 3 1， 中序：4 2 5 7 6 3 1，请画出整棵二叉树。

例3、已知先序：1 2 3 4 5 6， 后序：3 2 5 6 4 1， 请画所有二叉树的情况。

例4、如果只知道先序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？

例5、如果只知道中序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？

例6、如果只知道后序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？

练习

1. [2010提高（同2010普及）5] 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ B ）。{{ select(1) }}

• 0
• 2
• 4
• 6

2. [2009提高（同2009普及）6] 表达式a*(b+c)-d的后缀表达式是（ B ）。{{ select(2) }}

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

3. [2008提高16] 二叉树T，已知其先序遍历是1 2 4 3 5 7 6（数字为节点编号，以下同），后序遍历是4 2 7 5 6 3 1，则该二叉树的中根遍历不可能是（ C ）。{{ select(3) }}

• 4 2 1 7 5 3 6
• 2 4 1 7 5 3 6
• 4 2 1 7 5 6 3
• 2 4 1 5 7 3 6

4. [2008普及13] 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ B ）{{ select(4) }}

• 4 2 5 7 6 3 1
• 4 2 7 5 6 3 1
• 7 4 2 5 6 3 1
• 4 2 7 6 5 3 1

5. [2007提高12] 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同), 后根遍历是4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历 不可能 是( C ) {{ select(5) }}

• 4 2 6 5 1 7 3
• 4 2 5 6 1 3 7
• 4 2 3 1 5 6 7
• 4 2 5 6 1 7 3

6. [2007普及20] 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（  A ）{{ select(6) }}

• 4 6 5 2 7 3 1
• 4 6 5 2 1 3 7
• 4 2 3 1 5 4 7
• 4 6 5 3 1 7 2

7. [2006提高（同2006普及）14] （多选题）已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ BC ） {{ multiselect(7) }}

• 3 2 1 4 6 5
• 3 2 1 5 4 6
• 2 3 1 5 4 6
• 2 3 1 4 6 5

8. 前序遍历序列与中序遍历序列相同的二叉树为( D )。{{ select(8) }}

• 根结点无左子树
  
• 根结点无右子树
  
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

9. [CSP 2024 入门级第一轮 第 12 题] 已知二叉树的前序遍历为 [A,B,D,E,C,F,G]，中序遍历为 [D,B,E,A,F,C,G]，请问该二叉树的后序遍历结果是（ A ） {{ select(9) }}

• [D,E,B,F,G,C,A]
• [D,E,B,F,G,A,C]
• [D,B,E,F,G,C,A]
• [D,B,E,F,G,A,C]

10. [CSP 2023 入门级第一轮 第 8 题]后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是 ( A ) {{ select(10) }}

• ((6-(2+3))*(3+8/2))^2+3
• 6-2+3*3+8/2^2+3
• (6-(2+3))*((3+8/2)^2)+3
• 6-((2+3)*(3+8/2))^2+3

11.[CSP 2023 入门级第一轮 第 11 题] 给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是 ( A ) {{ select(11) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

12.[CSP 2022 入门级第一轮 第 6 题]对表达式 a+(b-c)*d 的前缀表达式为（ B ），其中 +、-、* 是运算符。 {{ select(12) }}

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d