注意
# 注意 上述两种算法为官方标准答案，当遍历到度为 1 的结点时，会传入空指针，导致空指针异常。但是，作为 408 考试的算法题，不要求考虑特殊的边界条件，只要算法思想正确，代码逻辑正确，即可得满分。因此，在复习过程中，无须花过多的时间报代码的各种边界条件。 # 16. 【解答】 1）算法的基本设计思想。 表达式树的中序序列加上必要的括号即等价的中缀表达式。可以基于二叉树的中序遍历策略 <!-- page: 179 --> 第5章 树与二叉树 167 得到所需的表达式。 表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）和操作数（对应叶结点）不需要添加括号。 2）算法实现。 将二叉树的中序遍历递归算法稍加改造即可得本题的答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，遍历完右子树后加上右括号。17. 【解答 1】 1）算法的基本设计思想。 对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值保存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 二叉搜索树需要满足的条件是：任意一个结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。 使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数。若当前遍历的结点值小于或等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。 2）算法实现。void BtreeToE(BTree *root) { BtreeToExp(root, 1); //根的高度为 1 } void BtreeToExp( BTree *root, int deep) { if (root == NULL) return; //空结点返回 else if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL) //若为叶结点 printf("%s", root-&gt;data); //输出操作数，不加括号 else { if (deep &gt; 1) printf(" ("); //若有子表达式则加一层括号 BtreeToExp(root-&gt;left, deep + 1); printf("%s", root-&gt;data); //输出操作符 BtreeToExp(root-&gt;right, deep + 1); if (deep &gt; 1) printf(" (")); //若有子表达式则加一层括号 } }【解答 2】 1）算法的基本设计思想。 对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值保存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 <!-- page: 180 --> 2027年数据结构考研复习指导 二叉搜索树需要满足的条件是：任意一个结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。设置两个数组 pmax 和 pmin。根据二叉搜索树的定义，SqBiTNode[i] 中的值应该大于以 SqBiTNode[2i+1] 为根的子树中的最大值（保存在 pmax[2i+1] 中），小于以 SqBiTNode[2i+2] 为根的子树中的最小值（保存在 pmin[2i+1] 中）。初始时，用数组 SqBiTNode 中前 ElemNum 个元素的值对数组 pmax 和 pmin 初始化。 在数组 SqBiTNode 中从后向前扫描，扫描过程中逐一验证结点与子树之间是否满足上述的大小关系。 2）算法实现。#define false 0 #define true 1 typedef int bool; bool judgeInOrderBST(SqBiTree bt, int k, int *val) { //初始调用时 k 的值是 0 if (k &lt; bt.ElemNum &amp;&amp; bt.SqBiTNode[k] != -1) { if (!judgeInOrderBST(bt, 2*k + 1, val)) return false; if (bt.SqBiTNode[k] &lt;= *val) return false; *val = bt.SqBiTNode[k]; if (!judgeInOrderBST(bt, 2*k + 2, val)) return false; } return true; }## 5.4 树、森林 ### 5.4.1 树的存储结构 树的存储方式有多种，既可采用顺序存储结构，也可采用链式存储结构。无论采用何种方式，都必须能够唯一地反映树中各结点之间的逻辑关系。下面介绍三种常用的存储结构。 #### 1. 双亲表示法 双亲表示法使用一组连续的存储空间（如数组）来存放树中的所有结点。每个结点除包含数据域外，还增设一个“伪指针”域，用于指示其双亲结点在数组中的下标。如图 5.20 所示，根结点位于下标 0 处，其双亲域设为 -1，表示无双亲。 双亲表示法的存储结构定义如下： //结点数#define false 0 #define true 1 typedef int bool; bool judgeBST(SqBiTree bt){ int k,m,*pmin,*pmax; pmin=(int *)malloc(sizeof(int)*(bt.ElemNum)); pmax=(int *)malloc(sizeof(int)*(bt.ElemNum)); for(k=0;k&lt;bt.ElemNum;k++) //辅助数组初始化 pmin[k]=pmax[k]=bt.SqBiTNode[k]; for(k=bt.ElemNum-1;k&gt;0;k--){ //从最后一个叶结点向根遍历 if(bt.SqBiTNode[k]!=-1){ m=(k-1)/2; //双亲 if(k%2==1&amp;&amp;bt.SqBiTNode[m]&gt;pmax[k]) //其为左孩子 pmin[m]=pmin[k]; else if(k%2==0&amp;&amp;bt.SqBiTNode[m]&lt;pmin[k]) //其为右孩子 pmax[m]=pmax[k]; else return false; } } return true; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 一棵树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 双亲表示
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 双亲指针图示 图5.20 树的双亲表示法 双亲表示法利用了每个结点（除根结点外）有且仅有一个双亲的性质。因此，查找任意结点的双亲非常高效；然而，查找某结点的孩子则需遍历整个数组，效率较低。 ## 注意 区分树与二叉树的顺序存储结构。在树的双亲表示法中，数组下标用于标识结点，结点间的父子关系通过 parent 域显式记录。而在二叉树的顺序存储结构中（如完全二叉树的数组表示），下标隐含了父子关系（例如，结点 $i$ 的左孩子为 $2i + 1$，右孩子为 $2i + 2$）。二叉树是树的特例，因此可以使用树的存储结构表示。但是，一般的树不能直接使用二叉树的顺序存储方式。 ## 2. 孩子表示法 孩子表示法将每个结点的所有孩子视为一个线性表，并用单链表存储。整棵树则由 $n$ 个这样的孩子链表组成（叶结点对应空链表）。为便于访问，所有孩子链表的头指针被集中存放在一个顺序表（如数组）中，每个位置对应一个结点。图5.21(a)展示了图5.20(a)中树的孩子表示法。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 孩子表示法 图5.21 树的孩子表示法和孩子兄弟表示法
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 孩子兄弟表示法 与双亲表示法相反，孩子表示法便于查找结点的孩子，但若要查找某结点的双亲，则需遍历所有孩子链表，检查是否包含该结点，效率较低。 ## 3. 孩子兄弟表示法 孩子兄弟表示法也称二叉树表示法，采用二叉链表作为树的存储结构。每个结点包含三部分： <!-- page: 182 --> 2027年数据结构考研复习指导 数据域、指向第一个孩子的指针、指向下一个兄弟的指针（沿此指针可依次访问该结点的所有右侧兄弟），如图5.21(b)所示。这种结构以“左孩子-右兄弟”的方式，将树映射为二叉树形式。 孩子兄弟表示法的存储结构描述如下： 孩子兄弟表示法具有良好的灵活性，其最大优点是能自然地将树转换为二叉树，从而复用二叉树的算法。查找孩子非常高效。然而，从当前结点高效回溯到其双亲较为困难。若在结点中增设一个parent指针域，则可高效查询双亲，形成一种三叉链表的存储结构。 ## 5.4.2 树、森林与二叉树的转换 二叉树和树均可用二叉链表作为存储结构。从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法完全相同，因此可以用同一存储结构的不同解释将一棵树转换为二叉树。 ### 1. 树转换为二叉树 **考点说法** 树和二叉树的转换及相关性质的推理（2009、2011） 树转换为二叉树的规则：每个结点的左指针指向其第一个孩子；右指针指向其在原树中的下一个右兄弟，这个规则也被称为“左孩子-右兄弟”原则。由于根结点没有兄弟，因此由树转换而来的二叉树的根结点必无右子树，如图5.22所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.22 树与二叉树的对应关系 树转换为二叉树的手工画法： 1）在所有兄弟结点之间添加连线； 2）对每个结点，仅保留其与第一个孩子的连线，删除与其他孩子的连线； 3）以树根为轴心，顺时针旋转 45°，使其呈现二叉树形态。 ### 2. 森林转换为二叉树 **考点说法** 森林和二叉树的转换及相关性质的推理（2014） 森林是若干棵树的集合，其转换基于单棵树的转换方法。首先将森林中的每棵树分别转换为 <!-- page: 183 --> 第5章 树与二叉树 171 对应的二叉树；由于每棵转换后的二叉树根结点均无右子树，可将这些根结点视为兄弟；将第二棵二叉树作为第一棵二叉树根的右子树……以此类推，最终形成一棵完整的二叉树。 森林转换为二叉树的手工画法： 1）将森林中的每棵树转换为相应的二叉树； 2）每棵树的根也可视为兄弟关系，在各树的根之间依次添加连线； 3）以第一棵树的根为轴心，顺时针旋转 45°。 等效做法是：先在各树的根之间添加连线，然后整体应用树转二叉树的方法处理。 ## 3. 二叉树转换为森林 **等效提及** ⊙ 由遍历序列构造一棵二叉树并转换为对应的森林（2020、2021） 若给定的二叉树非空，则其转换为森林的规则：二叉树的根及其左子树对应第一棵树的二叉树表示；将根的右指针断开，其右子树即代表剩余森林转换后的二叉树；对右子树递归应用相同规则，不断分离出下一棵树，直至右子树为空；最后将每棵分离出的二叉树还原为普通树，即可得到原始森林。此过程如图5.23所示。二叉树转换为树或森林的结果是唯一的。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.23 森林与二叉树的对应关系
## 5.4.3 树和森林的遍历
### 1. 树的遍历
**等效提及** ⊙ 树与二叉树遍历方法的对应关系（2019）
树的遍历是指以某种方式访问树中的每个结点，且仅访问一次。主要有两种方式：
1）先根遍历。若树非空，则按如下规则遍历：
- 先访问根结点。
- 再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。
其遍历序列与这棵树相应二叉树的先序序列相同。
2）后根遍历。若树非空，则按如下规则遍历：
- 先依次遍历根结点的每棵子树，遍历子树时仍遵循先子树后根的规则。
- 再访问根结点。
其遍历序列与这棵树相应二叉树的中序序列相同。
图5.22的树的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。
此外，树也支持层次遍历，与二叉树的层次遍历原理相似，即按层序依次访问各个结点。
### 2. 森林的遍历
基于森林和树相互递归的定义，可得出森林的两种遍历方法。
<!-- page: 184 -->
2027年数据结构考研复习指导
1）先序遍历森林。若森林为非空，则按如下规则遍历：
- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树后的剩余森林。
2）中序遍历森林。若森林为非空，则按如下规则遍历：
- 中序遍历第一棵树中根结点的子树森林。
- 访问森林中第一棵树的根结点。
- 中序遍历除去第一棵树后的剩余森林。
图5.23的森林的先序遍历序列为 $ABCDEFGHI$，中序遍历序列为 $BCDAFEHIG$。
**考点点击：** 森林与二叉树遍历方法的对应关系（2020）
当森林转换成二叉树时，第一棵树的子树森林会转换为左子树，剩余森林则转换为右子树。因此，森林的先序、中序遍历与其对应二叉树的先序、中序遍历相同。
树和森林的遍历与二叉树的遍历关系见表5.1。
表 5.1 树和森林的遍历与二叉树遍历的对应关系
| 树 | 森林 | 二叉树 |
| --- | --- | --- |
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
**注意**
森林遍历方法的命名按照严蔚敏老师的教材。有些教材也将森林的中序遍历称为后序遍历，称中序遍历是相对其二叉树而言的，称后序遍历是因为根确实是在最后才被访问的。
## 5.4.4 本节试题精选
### 一、单项选择题
01. 下列关于树的说法中，正确的是（）。
I. 对于有 $n$ 个结点的二叉树，其高度为 $\log_2 n$
II. 完全二叉树中，若一个结点没有左孩子，则它必是叶结点
III. 高度为 $h(h > 0)$ 的完全二叉树对应的森林所含的树的个数一定是 $h$
IV. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数
A. I 和 III
B. IV
C. I 和 II
D. II
02. 利用二叉链表存储森林时，根结点的右指针是（）。
A. 指向最左兄弟
B. 指向最右兄弟
C. 一定为空
D. 不一定为空
03. 设森林 $F$ 中有 3 棵树，第 1、2、3 棵树的结点数分别为 $M_1, M_2$ 和 $M_3$，与森林 $F$ 对应的二叉树根结点的右子树上的结点数是（）。
A. $M_1$
B. $M_1 + M_2$
C. $M_3$
D. $M_2 + M_3$
04. 设森林 $F$ 中有 4 棵树，第 1、2、3、4 棵树的结点数分别为 $a$、$b$、$c$ 和 $d$，与森林 $F$ 对应的二叉树的根结点的左子树上的结点数是（）。
A. $a$
B. $b + c + d$
C. $a - 1$
D. $a + b + c$
05. 设森林 $F$ 对应的二叉树为 $B$，它有 $m$ 个结点，$B$ 的根为 $p$，$p$ 的右子树结点数为 $n$，森林 $F$ 中第一棵树的结点数是（）。
<!-- page: 185 -->
第5章 树与二义树
173
A. $m - n$
B. $m - n - 1$
C. $n + 1$
D. 条件不足，无法确定
06. 设森林 $F$ 对应的二义树是一棵具有 16 个结点的完全二义树，则森林 $F$ 中树的数目和结点最多的树的结点数分别是（）。
A. 2 和 8
B. 2 和 9
C. 4 和 8
D. 4 和 9
07. 森林 $T = (T_{1}, T_{2}, \dots, T_{m})$ 转化为二义树 BT 的过程为：若 $m = 0$，则 BT 为空，若 $m \neq 0$，则（）。
A. 将中间子树 $T_{\mathrm{mid}}$（$\mathrm{mid} = (1 + m) / 2$）的根作为 BT 的根；将 $(T_{1}, T_{2}, \dots, T_{\mathrm{mid}-1})$ 转换为 BT 的左子树；将 $(T_{\mathrm{mid}+1}, \dots, T_{m})$ 转换为 BT 的右子树
B. 将子树 $T_{1}$ 的根作为 BT 的根；将 $T_{1}$ 的子树森林转换成 BT 的左子树；将 $(T_{2}, T_{3}, \dots, T_{m})$ 转换成 BT 的右子树
C. 将子树 $T_{1}$ 的根作为 BT 的根；将 $T_{1}$ 的左子树森林转换成 BT 的左子树；将 $T_{1}$ 的右子树森林转换为 BT 的右子树；其他以此类推
D. 将森林 $T$ 的根作为 BT 的根；将 $(T_{1}, T_{2}, \dots, T_{m})$ 转化为该根下的结点，得到一棵树，然后将这棵树再转化为二义树 BT
08. 设 $F$ 是一个森林，$B$ 是由 $F$ 变换来的二义树。若 $F$ 中有 $n$ 个非终端结点，则 $B$ 中右指针域为空的结点有（）个。
A. $n - 1$
B. $n$
C. $n + 1$
D. $n + 2$
09. 设某树的孩子兄弟链表示中共有 6 个空的左指针域、7 个空的右指针域，包括 5 个结点的左右指针域都为空，则该树中叶结点的个数是（）。
A. 7
B. 6
C. 5
D. 不能确定
10. 若 $T_{1}$ 是由有序树 $T$ 转换而来的二义树，则 $T$ 中结点的后根序列就是 $T_{1}$ 中结点的（ ）序列。
A. 先序
B. 中序
C. 后序
D. 层序
11. 某二义树结点的中序序列为 $BDAECF$，后序序列为 $DBEFCA$，则该二义树对应的森林包括（ ）棵树。
A. 1
B. 2
C. 3
D. 4
12. 设 $X$ 是树 $T$ 中的一个非根结点，$B$ 是 $T$ 所对应的二义树。在 $B$ 中，$X$ 是其双亲结点的右孩子，下列结论中正确的是（）。
A. 在树 $T$ 中，$X$ 是其双亲结点的第一个孩子
B. 在树 $T$ 中，$X$ 一定无右边兄弟
C. 在树 $T$ 中，$X$ 一定是叶结点
D. 在树 $T$ 中，$X$ 一定有左边兄弟
13. 右图是一棵逻辑上的树 $T$，则在关于该树的存储结构的叙述中，错误的是（）。
A. 若 $T$ 采用双亲表示法，则有 9 个指向双亲的指针
B. 若 $T$ 采用孩子表示法，则在 $T$ 中查找某个结点的孩子比双亲表示法更方便
C. 若 $T$ 采用孩子兄弟表示法，则在 $T$ 中查找某个结点的双亲的时间复杂度为 $O(1)$
D. 双亲表示法是顺序存储结构，孩子表示法和孩子兄弟表示法通常是链式存储结构
14. 在森林的二义树表示中，结点 $M$ 和结点 $N$ 是同一父结点的左孩子和右孩子，则在该森林中（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 186 --> 2027年数据结构考研复习指导 A. $M$ 和 $N$ 有同一双亲 B. $M$ 和 $N$ 可能无公共祖先 C. $M$ 是 $N$ 的孩子 D. $M$ 是 $N$ 的左兄弟 15. 【2009 统考真题】将森林转换为对应的二叉树，若在二叉树中，结点 $u$ 是结点 $v$ 的父结点的父结点，则在原来的森林中，$u$ 和 $v$ 可能具有的关系是（ ）。 I. 父子关系 II. 兄弟关系 III. $u$ 的父结点与 $v$ 的父结点是兄弟关系 A. 只有 II B. I 和 II C. I 和 III D. I、II 和 III 16. 【2011 统考真题】已知一棵有 2011 个结点的树，其叶结点数为 116，该树对应的二叉树中无右孩子的结点数是（ ）。 A. 115 B. 116 C. 1895 D. 1896 17. 【2014 统考真题】将森林 $F$ 转换为对应的二叉树 $T$，$F$ 中叶结点的个数等于（ ）。 A. $T$ 中叶结点的个数 B. $T$ 中度为 1 的结点数 C. $T$ 中左孩子指针为空的结点数 D. $T$ 中右孩子指针为空的结点数 18. 【2019 统考真题】若将一棵树 $T$ 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 $T$ 的后根遍历序列相同的是（ ）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 19. 【2020 统考真题】已知森林 $F$ 及与之对应的二叉树 $T$，若 $F$ 的先根遍历序列是 $a, b, c, d, e, f$，后根遍历序列是 $b, a, d, f, e, c$，则 $T$ 的后序遍历序列是（ ）。 A. $b, a, d, f, e, c$ B. $b, d, f, e, c, a$ C. $b, f, e, d, c, a$ D. $f, e, d, c, b, a$ 20. 【2021 统考真题】某森林 $F$ 对应的二叉树为 $T$，若 $T$ 的先序遍历序列是 $a, b, d, c, e, g, f$，中序遍历序列是 $b, d, a, e, g, c, f$，则 $F$ 中树的棵数是（ ）。 A. 1 B. 2 C. 3 D. 4 21. 【2025 统考真题】下列关于二叉树及森林的叙述中，正确的是（ ）。 A. 完全二叉树中不存在度为 1 的结点 B. 任意一个森林都可以转换为一棵二叉树 C. 二叉树的分支结点数比叶结点数少 D. 表达式树的根中保存的是最先计算的运算符