二、综合应用题
## 二、综合应用题 01. 给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？若能，请举例说明；若不能，请给出反例。 02. 将下面一个由 3 棵树组成的森林转换为二叉树。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
03. 已知某二叉树的先序序列和中序序列分别为 ABDEHCFIMGJKL 和 DBHEAIMFCGKLJ，请画出这棵二叉树，并画出二叉树对应的森林。 04. 编程水以孩子兄弟表示法存储的森林的叶结点数。 05. 以孩子兄弟链表为存储结构，请设计递归算法水树的深度。 <!-- page: 187 --> 第5章 树与二叉树 175 ## 5.4.5 答案与解析 ### 一、单项选择题 #### 01. D 若 $n$ 个结点的二叉树是一棵单叉树，则其高度为 $n$。完全二叉树中最多存在一个度为1的结点且只有左孩子，若不存在左孩子，则一定也不存在右孩子，因此必是叶结点，说法II正确。只有满二叉树才具有性质III，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 满二叉树转化为对应的森林
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 非满二叉树转化为对应的森林 在树转换为二叉树时，若有几个叶结点具有共同的双亲，则转换成二叉树后只有一个叶结点（最右边的叶结点），如下图所示，说法IV错误。注意，若树中的任意两个叶结点都不存在相同的双亲，则树中的叶子数才有可能与其对应的二叉树中的叶子数相等。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
#### 02. D
森林与二叉树具有对应关系，因此，我们存储森林时应先将森林转换成二叉树，转换的方法就是“左孩子右兄弟”，与树不同的是，若存在第二棵树，则二叉链表的根结点的右指针指向的是森林中的第二棵树的根结点。若此森林只有一棵树，则根结点的右指针为空。因此，右指针可能为空也可能不为空。
#### 03. D
与树转换为二叉树不同，森林中的每棵树是独立的，因此先要将每棵树的根结点全部视为兄弟结点的关系。森林转换为二叉树后，树2作为树1的根结点的右子树，树3作为树2的根结点的右子树，因此森林 $F$ 对应的二叉树根结点的右子树上的结点数是 $M_{2} + M_{3}$。
#### 04. C
森林转换为二叉树后，二叉树的根结点为第1棵树的根结点，二叉树的根结点的左子树包含第1棵树的所有孩子，因此森林 $F$ 对应的二叉树的根结点的左子树上的结点数是 $a - 1$。
#### 05. A
森林转换成二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树。右子树为其他剩余的树。所以，第一棵树的结点数为 $m - n$。
#### 06. D
森林转换为二叉树后，二叉树的根结点及其左子树由第1棵树转换得到，二叉树的根结点的右子树由剩余的森林转换得到，以此类推，可以划分出第2, 3, …棵树的结点。具有16个结点的完全二叉树的形态如右图所示，沿二叉树的根结点往右下遍历，共有4个结点，可知森林中有4棵树，其中第1棵树的结点数最多，
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 188 -->
2027年数据结构考研复习指导
有9个。
07. B
将森林中每棵树的根结点视为兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化。
08. C
根据森林与二叉树转换规则“左孩子右兄弟”。二叉树 $B$ 中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，所以树 $B$ 中右指针域为空的结点有 $n + 1$ 个。
09. B
在树的孩子兄弟表示法中，若一个结点没有孩子（叶结点），则表现为该结点的左指针域为空，因此本题答案为“6”。至于“5个结点的左右指针域都为空”，表示树中有5个结点既没有孩子又没有右兄弟，约束条件比题中的“求叶结点的个数”要求更严格。
10. B
有序树 $T$ 转换成二叉树 $T_{1}$ 时，$T$ 的后根序列是对应 $T_{1}$ 的中序序列还是后序序列呢（显然树的后根序列不可能对应二叉树的先序序列和层序序列）？看右图所示的例子，在树 $T$ 中，叶结点 $B$ 应最先访问，在 $T_{1}$ 中，$B$ 的右兄弟 $C$ 转换为它的右孩子，若对应 $T_{1}$ 的后序序列，则 $C$ 应在 $B$ 的前面访问，所以 $T$ 的后根序列不可能对应 $T_{1}$ 的后序序列。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
11. C 根据二叉树的先序序列和中序序列可以确定一棵二叉树。根据后序序列，$A$ 是二叉树的根结点。根据中序序列，二叉树的形态如下图(a)所示。对于 $A$ 的左子树，根据后序序列，$B$ 比 $D$ 后被访问，因此 $B$ 必为 $D$ 的父结点，又根据中序序列，$D$ 是 $B$ 的右孩子。对于 $A$ 的右子树，同理可确定结点 $E$、$C$、$F$ 的关系。此二叉树的形态如下图(b)所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
再根据二叉树与森林的对应关系，森林中树的棵数即其对应二叉树（向右上旋转 $45^{\circ}$ 后）的根结点 $A$ 及其右兄弟数，或解释为：对应二叉树从根结点 $A$ 开始不断往右孩子访问，所访问到的结点数。可知此森林中有3棵树，根结点分别为 $A$、$C$ 和 $F$。
12. D
在二叉树 $B$ 中，$X$ 是其双亲的右孩子，因此在树 $T$ 中，$X$ 必是其双亲结点的右兄弟，换句话说，$X$ 在树中必有左兄弟。
13. C
若 $T$ 采用双亲表示法存储，则除根结点外，其余每个结点都有指向其双亲的指针，$T$ 共有10个结点，于是有9个指向双亲的指针，选项A正确。若 $T$ 采用孩子表示法存储，则每个结点的孩子被视为一个线性表，且以单链表作为存储结构，只要遍历该单链表，就能找到某个结点的所有孩子，而双亲表示法要寻找某个结点的孩子，就必须遍历整棵树，选项B正确。若 $T$ 采用孩子兄
<!-- page: 189 -->
第5章 树与二叉树
177
弟表示法，则在 $T$ 中查找某个结点的双亲也必须遍历整棵树，时间复杂度为 $O(n)$，选项C错误。选项D显然正确。
14. B
在森林的二叉树表示中，当 $M$ 和 $N$ 的父结点是二叉树根结点时，$M$ 和 $N$ 在不同的树上。因此 $M$ 和 $N$ 可能无公共祖先。
15. B
森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或者原本就是父子关系。
说法I：若结点 $\nu$ 是结点 $u$ 的第二个孩子结点，转换时，结点 $\nu$ 就变成结点 $u$ 第一个孩子的右孩子，符合要求。说法II：结点 $u$ 和 $\nu$ 是兄弟结点的关系，但二者之中还有一个兄弟结点 $k$，则转换后结点 $\nu$ 就变为结点 $k$ 的右孩子，而结点 $k$ 则是结点 $u$ 的右孩子，符合要求。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图I
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图II 说法III：若结点 $u$ 的父结点与 $\nu$ 的父结点是兄弟关系，则转换后，结点 $u$ 和 $\nu$ 分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图III
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
【另解】由题意可知 $u$ 是 $\nu$ 的父结点的父结点，如下图所示，有四种情况：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(1)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(2)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(3)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(4) 根据树与二叉树的转换规则，将这四种情况转换成树中结点的关系。（1）在原来的树中 $u$ 是 $\nu$ 的父结点的父结点；（2）在树中 $u$ 是 $\nu$ 的父结点；（3）在树中 $u$ 是 $\nu$ 的父结点的兄弟；（4）在树中 $u$ 与 $\nu$ 是兄弟关系。由此可知说法I和II正确。 16. D 树转换为二叉树时，树的每个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应二叉树中无右孩子的结点数 = 分支结点数 + 1 = 2011 - 116 + 1 = 1896。 通常本题应采用特殊法求解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，所以无右孩子的结点数 = 2011 - 115 = 1896。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
共1895个中间结点 共116个叶结点 17. C 将森林转化为二叉树相当于用孩子兄弟表示法来表示森林。在变化过程中，原森林某结点的 <!-- page: 190 --> 2027年数据结构考研复习指导 第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。森林中的叶结点没有孩子结点，转化为二叉树时，该结点就没有左结点，因此 $F$ 中叶结点的个数等于 $T$ 中左孩子指针为空的结点数。此题还可通过一些特例来排除选项 A、B 和 D。 ## 18. B 后根遍历树可分为两步：① 从左到右访问双亲结点的每个孩子（转化为二叉树后，先访问根结点，再访问右子树）；② 访问完所有孩子后，再访问它们的双亲结点（转化为二叉树后，先访问左子树，再访问根结点），因此树的后根遍历序列与其相应二叉树的中序遍历序列相同。对于此类题，采用特殊值法求解通常会更便捷，左下图树 $T$ 转换为二叉树 BT 的过程如下图所示，树的后序遍历序列显然和其相应二叉树的中序遍历序列相同，均为 5,6,7,2,3,4,1。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 19. C 森林 $F$ 的先根遍历序列对应于其二叉树 $T$ 的先序遍历序列，森林 $F$ 的后根遍历序列对应于其二叉树 $T$ 的中序遍历序列。即 $T$ 的先序遍历序列为 $a, b, c, d, e, f$，中序遍历序列为 $b, a, d, f, e, c$。根据二叉树 $T$ 的先序序列和中序序列可以唯一确定它的结构，构造过程如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
可以得到二叉树 $T$ 的后序序列为 $b, f, e, d, c, a$。 ## 20. C 由二叉树 $T$ 的先序序列和中序序列可以构造出 $T$，如右图所示。由森林转化成二叉树的规则可知，森林中每棵树的根结点以右子树的方式相连，所以 $T$ 中的结点 $a、c、f$ 为 $F$ 中树的根结点，森林 $F$ 中有3棵树。 ## 21. B 完全二叉树中至多存在一个度为1的结点（最后一个非叶结点仅当总结点数为偶数时出现），选项A错误。根据“左孩子右兄弟”表示法，
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
任意森林均可唯一地转换为一棵二叉树，即将每棵树的根视为兄弟，各树内部按左孩子、右兄弟关系重构，选项B正确。在任意非空二叉树中，叶结点数 $n_0$ 等于度为2的结点数 $n_2$ 加1。但分支结点包括度为1和度为2的结点，其总数不一定少于叶结点数。例如，一条单支二叉树中，叶结点仅1个，而分支结点有 $n - 1$ 个，远多于叶结点。选项C错误。表达式树的结构体现运算优先级，根结点对应最后执行的运算符，而非最先计算的。最先计算的操作位于最深层的子树中，选项D错误。 <!-- page: 191 --> 第5章 树与二叉树 179 ## 二、综合应用题 ### 01. 【解答】 一棵树的先根遍历结果与其对应二叉树的先序遍历结果相同，树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。二叉树的先序序列和中序序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根遍历序列和后根遍历序列能够唯一地确定这棵树。例如，对于右图所示的树，对应二叉树的先序序列为1,2,3,4,5,6,8,7，中序序列为3,4,8,6,7,5,2,1。原树的先根遍历序列为1,2,3,4,5,6,8,7，后根遍历序列为3,4,8,6,7,5,2,1。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
**注意** 树的先根遍历、后根遍历与对应二叉树的先序遍历、中序遍历对应。 ### 02. 【解答】 根据树与二叉树“左孩子右兄弟”的转换规则，将森林转换为二叉树的过程如下：① 将每棵树的根结点也视为兄弟关系，在兄弟结点之间加一连线。② 对每个结点，只保留它与第一个子结点的连线，与其他子结点的连线全部抹掉。③ 以树根为轴心，顺时针旋转 45°。结果如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
### 03. 【解答】 知道二叉树的先序和中序遍历后，可以唯一确定这棵树的结构。然后把二叉树转换到树和森林的方式是，若结点 x 是双亲 y 的左孩子，则把 x 的右孩子、右孩子的右孩子……都与 y 用连线连起来，最后去掉所有双亲到右孩子的连线。 得到的二叉树及对应的森林如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 192 --> 2027年数据结构考研复习指导 ## 04. 【解答】 当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=NULL），则它必是叶子，总的叶结点数是孩子子树（fch）上的叶子数和兄弟子树（nsib）上的叶结点数之和。 算法代码如下：## 05. 【解答】 由孩子兄弟链表表示的树，求高度的算法思想：采用递归算法，若树为空，高度为零；否则，高度为第一个孩子树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。算法代码如下： ## 5.5 树与二叉树的应用 ### 5.5.1 哈夫曼树和哈夫曼编码 #### 1. 哈夫曼树的定义 在介绍哈夫曼树之前，先明确几个相关概念： 在许多实际应用中，树中的结点常被赋予一个具有特定意义的数值，称为该结点的权。 从树的根结点到某一结点的路径长度与该结点权值的乘积，称为该结点的带权路径长度。 树中所有叶结点的带权路径长度之和称为该树的带权路径长度（WPL），记为 $$ \mathrm{WPL} = \sum_{i=1}^{n} w_i l_i $$ 式中，$w_i$ 为第 $i$ 个叶结点的权值，$l_i$ 为该叶结点到根结点的路径长度。 <!-- page: 193 --> 第5章 树与二叉树 181 若将各叶结点的权值视为其出现的频度或概率，则每个叶结点的路径长度以其权值为权重所计算出的加权平均值称为加权平均长度，记为 加权平均长度 = WPL / 各叶结点的权值之和 在含有 $n$ 个带权叶结点的二叉树中，WPL 最小的二叉树称为哈夫曼树，也称最优二叉树。图 5.24 中的 3 棵二叉树均包含 4 个叶结点 $a, b, c, d$，权值分别为 $7, 5, 2, 4$，对应的 WPL 分别为typedef struct node { ElemType data; //数据域 struct node *fch, *nsib; //孩子与兄弟域 } *Tree; int Leaves(Tree t) { //计算以孩子兄弟表示法存储的森林的叶子数 if (t == NULL) return 0; //树空返回 0 if (t-&gt;fch == NULL) //若结点无孩子，则该结点必是叶子 return 1 + Leaves(t-&gt;nsib); //返回叶结点和其兄弟子树中的叶结点数 else //孩子子树和兄弟子树中叶子数之和 return Leaves(t-&gt;fch) + Leaves(t-&gt;nsib); }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)
图 5.24 具有不同带权路径长度的二叉树
(a) $\mathrm{WPL} = 7 \times 2 + 5 \times 2 + 2 \times 2 + 4 \times 2 = 36$。
(b) $\mathrm{WPL} = 4 \times 2 + 7 \times 3 + 5 \times 3 + 2 \times 1 = 46$。
(c) $\mathrm{WPL} = 7 \times 1 + 5 \times 2 + 2 \times 3 + 4 \times 3 = 35$。
其中，图 5.24(c) 树的 WPL 最小，可验证其恰好为对应权值集合的哈夫曼树。
## 2. 哈夫曼树的构造
给定 $n$ 个权值分别为 $w_{1}, w_{2}, \cdots, w_{n}$ 的结点，构造哈夫曼树的步骤如下：
1）将这 $n$ 个结点分别视为 $n$ 棵仅含一个结点的二叉树，构成森林 $F$。
**哈夫曼树** ▶ 分析哈夫曼树的路径上权值序列的合法性（2010）
2）构造一个新结点，从 $F$ 中选取两棵根结点权值最小的树作为其左右子树，并将新结点的权值设为左右子树根结点的权值之和。
3）从 $F$ 中删除所选的两棵树，并将新生成的树加入 $F$。
4）重复步骤 2）和 3），直至 $F$ 中仅剩一棵树为止，最终得到的树即为哈夫曼树。
**哈夫曼树** ▶ 哈夫曼树的性质（2010、2019）
由上述构造过程可归纳出哈夫曼树的以下性质：
1）每个初始结点最终都成为叶结点，且权值越小的结点，其到根的路径长度越大。
2）构造过程中共新建了 $n - 1$ 个结点（双分支结点），因此哈夫曼树的结点总数为 $2n - 1$。
3）每次合并均选取两棵树，故哈夫曼树中不存在度为 1 的结点（为严格二叉树）。
例如，权值集合 $\{7, 5, 2, 4\}$ 的哈夫曼树构造过程如图 5.25 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.25 哈夫曼树的构造过程 <!-- page: 194 --> 2027年数据结构考研复习指导 # 3. 哈夫曼编码 在数据通信中，若对每个字符使用相同长度的二进制位表示，称这种编码方式为固定长度编码；若允许不同字符使用不同长度的二进制位表示，则称为可变长度编码。合理的可变长度编码（如哈夫曼编码）比固定长度编码要好得多，其特点是对出现频率高的字符赋予较短编码，而对频率低的字符赋予较长编码，从而降低字符的平均编码长度，起到压缩数据的效果。 ## 考察成绩 根据哈夫曼编码对编码序列进行译码（2017） 若一个编码集合中，没有任何一个编码是另一个编码的前缀，则称该编码为前缀编码。例如，为字符 A, B 和 C 分配编码 0, 10 和 110，这是一个前缀编码。由于编码互不为前缀，解码过程简单且无歧义：从左到右扫描码串，一旦识别出一个有效编码，即可立即译出对应字符。例如，码串 0010110 可唯一译为 A A B C。反之，若再为字符 D 分配编码 11，则 11 是 110 的前缀，导致上述码串的后 3 位无法确定是 D A，还是直接表示 C，从而破坏唯一可译性。 ## 考察成绩 哈夫曼树的构造及相关的分析（2012、2018、2021、2023） ## 考察成绩 前缀编码的分析及应用（2014、2020） 可利用二叉树设计二进制前缀编码。例如，为字符 A, B, C, D 设计前缀编码，可用图 5.26 所示的二叉树表示：四个叶结点分别对应这四个字符，并约定左分支标记为 0，右分支标记为 1。将根到各叶结点路径上的分支标记（0/1）拼接成的字符串，作为对应字符的编码，字符 A, B, C, D 的编码分别为 0, 10, 110, 111。可以证明，如此生成的编码必为前缀编码。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.26 前缀编码示例 ## 考察成绩 哈夫曼编码和定长编码的差异（2022） 哈夫曼编码是一种非常高效的数据压缩编码方法。由哈夫曼树生成哈夫曼编码的过程十分自然。首先，将每个字符视为一个独立的叶结点，其权值为其出现的频度（或次数）；构造对应的哈夫曼树；然后，将从根到各叶结点路径上分支标记的字符串，作为该字符的编码。图 5.27 展示了一个由哈夫曼树构造哈夫曼编码的示例，图中矩形结点标注了字符及其出现频次。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.27 由哈夫曼树构造哈夫曼编码
该哈夫曼树的 WPL 为
$$
\mathrm{WPL} = 1 \times 45 + 3 \times (13 + 12 + 16) + 4 \times (5 + 9) = 224
$$
此处的 WPL 表示对 100 个字符编码后的二进制总长度，共 224 位。若采用 3 位固定长度编码（共 6 个不同字符，需至少 3 位），则总长度为 $3 \times 100 = 300$ 位。因此，哈夫曼编码实现了约 $25\%$ 的数据压缩率。由此可见，利用哈夫曼树可以设计出总长度最短的二进制前缀编码。