Relax1000 数据结构 · 第5章 树 · 解析¶
第5章 树¶
本章 82 题；解析册印刷页 27–40。
速对答案（原书）： B D A B B D A D A B C C C D A C C C C C D B B C C D B A C D C A B D B A D D C C B B C C D D B C C A B D B D B B D D C D B D C A D C D A C D A B A C C D D D D B B D
Q1¶
速对表原值： B
详细解析标注： B
度数之和 + 1 = 结点总数。可以得到 81 + N2 = N0，N1 + N2 = 10，根据题目意思，N1和N2都至少存在一个，所以N2最多取到 9。N0最大是 81 + 9 = 90 个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
速对表原值： D
详细解析标注： D
度的总和+1=结点总数，设〔公式/符号见原页版面片段〕为度为 m 的节点个数，由题：〔公式/符号见原页版面片段〕3 = 2, 〔公式/符号见原页版面片段〕2 = 1, 〔公式/符号见原页版面片段〕1 = 7 所以 4〔公式/符号见原页版面片段〕4 + 3〔公式/符号见原页版面片段〕3 + 2〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕1 + 1 = 〔公式/符号见原页版面片段〕4 + 〔公式/符号见原页版面片段〕3 + 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕1 + 〔公式/符号见原页版面片段〕0 → 3〔公式/符号见原页版面片段〕4 − 〔公式/符号见原页版面片段〕0 =− 6
①，结点总数为 20，所以〔公式/符号见原页版面片段〕4 + 〔公式/符号见原页版面片段〕3 + 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕1 + 〔公式/符号见原页版面片段〕0 = 20 → 〔公式/符号见原页版面片段〕4 + 〔公式/符号见原页版面片段〕0 = 10
②，联立
①
②，解得〔公式/符号见原页版面片段〕0 = 9。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q3¶
速对表原值： A
详细解析标注： A
这样的树中至少有一个节点的度为 4，也就是说，至少有一层中有 4 个或 4 个以上的节点，因此，树的高度至多是 n-3。本题答案为 A。算最小高度应该用满 4 叉树来推。
Q4¶
速对表原值： B
详细解析标注： B
n 个结点 m 叉树，一共有 mn 个指针域，除了根节点没有父亲结点，其他 n-1 个结点都有唯一一条链指向它（一个分支对应一个子结点），所以使用的指针域有 n-1 个，空的指针域有〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕 − 1 = 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 + 1。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q5¶
速对表原值： B
详细解析标注： B
本题答案为 n=4 的卡特兰数。证明：利用卡特兰数的递推式：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 0 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 − 2 + ... + 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 0思想：确定根节点后，剩余 n-1 个结点各自分配在左右子树，形成以上卡特兰数的递推数学模型。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
速对表原值： D
详细解析标注： D
高度=结点数，说明每层只有一个结点，高度为 8 的二叉树，第 8 层最多容纳28−1 = 128 个结点，即第 8 层每个结点到根节点的路径都是符合本题的二叉树的树型。答案选 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
速对表原值： A
详细解析标注： A
二叉树中结点个数可以为 0，称为空树，所以 B 错。满二叉树中，任何一个结点的度，或者为 0，或者为 2。完全二叉树中，任何一个结点的度，或者为 0，或者为 1，或者为 2，所以 C错。二叉树的度可以是 0，1，2，所以 D 错
Q8¶
速对表原值： D
详细解析标注： D
设度为 0 和 2 的结点数分别为。在二叉树中，存在结论：分支数 + 1 = 结点数。在正则二叉树中不存在度为1的结点。则存在：2 × 〔公式/符号见原页版面片段〕2 + 1 = 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕0，可得出：〔公式/符号见原页版面片段〕2 = 〔公式/符号见原页版面片段〕0 − 1，〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕0 =〔公式/符号见原页版面片段〕，则。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q9¶
速对表原值： A
详细解析标注： A
二叉链表表示的二叉树中空指针的数量为 n+1，三叉链表表示的二叉树多了一个根结点指向双亲的空指针，所以树中空指针的数量为 n+2, Ⅰ正确。若根结点的度为 2，则只有左、右两个孩子指向它，Ⅱ错误。若整棵树只有一个根结点，则没有指针指向它，Ⅲ错误。
Q10¶
速对表原值： B
详细解析标注： B
采用排除法，由二叉树的性质知，若二叉树只有度为 0 和度为 2 的结点，则总结点是一个奇数，可以排除 A 和 C。当 h = 2 时，一个二叉树最多有结点数 2^2-1 = 3 个，而 D 项等于 5，可以排除 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
速对表原值： C
详细解析标注： C
A：不满足 n0 =n2 +1 的性质，所以不存在这样的二叉树。B：在完全二叉树中，n1 =0 或 1，而 n0=n2+1，所以分支节点个数 n1 +n2 =n0 或 n1 +n2 =n0-1。C：通过只有两个节点（其中 a 为根节点，b 为 a 的右孩子）的二叉树来验证本叙述是不正确的。D：在完全二叉树中，已知节点总数就可以确定其形状。已知其先序序列，便可知其节点总数，再根据先序序列确定每个节点的位置。实际上，只要已知完全二叉树的任一种遍历序列都可以唯一确定该二叉树。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
速对表原值： C
详细解析标注： C
当根结点下标为 1 时，下标为 i 的结点的父结点下标为 left lfloor i/2 right rfloor，那么下标为 17 的祖先的下标有 8, 4, 2, 1，下标为 19 的祖先的下标有 9, 4, 2, 1，因此两者最近的公共祖先的下标是 4。
Q13¶
速对表原值： C
详细解析标注： C
511 = 29 − 1 < 513 < 210 − 1 = 1023，所以层高最小应该是完全二叉树的形态，高度为 10，最高的树形是一条单链，层高为结点数 513，所以 10-513 都可以取到，答案为 513-10+1=504 种。思考：m 叉树呢？度为 m 的树呢？层高可能是多少种。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q14¶
速对表原值： D
详细解析标注： D
本题考查几种特殊二叉树的性质。对于 A 选项，满二叉树，设层数为 h，则2ℎ − 1 = 〔公式/符号见原页版面片段〕，求出 h，叶结点都在最后一层上，即叶结点数为2ℎ−1。对于 B 选项，在完全二叉树中，度为 1 的结点数为 0 或 1，〔公式/符号见原页版面片段〕 = 2〔公式/符号见原页版面片段〕0 + 〔公式/符号见原页版面片段〕1 + 1，则N0 = ⌊(〔公式/符号见原页版面片段〕 + 1)/2⌋。对于 C 选项，哈夫曼树只有度数为 2 和 0 的结点，〔公式/符号见原页版面片段〕0 = 〔公式/符号见原页版面片段〕2 + 1，〔公式/符号见原页版面片段〕0 + 〔公式/符号见原页版面片段〕2 = 〔公式/符号见原页版面片段〕，即〔公式/符号见原页版面片段〕0 = 〔公式/符号见原页版面片段〕 + 1 /2可得叶结点个数。对于 D 选项，则无法求出叶结点个数。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
速对表原值： A
详细解析标注： A
度为 0 的比度为 2 的结点多一个，度为 0 的结点 30 个，所以度为 2 的结点 29个，度为 1 的结点 20 个，所以一共有 30+29+20=79 个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
速对表原值： C
详细解析标注： C
完全二叉树这种题目，因为叶子结点只可能在最后一层和倒数第二层，所以既可以问最多的情况，也可以问最少的情况。最多的情况：8个叶子是倒数第二层上的叶子数量。这时候倒数第二层是第6层，一共有26−1 = 32个结点，分支结点有 32-8=24 个结点，最多的情况就是这 26 个分支结点都有 2 个孩子，也就是前 6 层是满二叉树，最后一层有 24*2=48 个叶子结点的情况，最多有26 − 1 + 48 = 111 个结点。最少的情况：8 个叶子是最后一层上的叶子数量，由完全二叉树的性质，前 5 层节点总数由满二叉树公式25 − 1 = 31，加上第 6 层，最少 31+8=39 个结点。
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：改数字
解析已算出第 6 层 32 个位置中有 8 个叶结点，因而分支结点应为 32-8=24；后文“26 个分支结点”是笔误，应为 24。王道同题回源：result.md [block: b_150_4]。
Q17¶
速对表原值： C
详细解析标注： C
完全二叉树一共有 8 个叶结点，而普通二叉树最少可以有 1 个叶结点(单链)，相差最大 8-1=7。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
速对表原值： C
详细解析标注： C
I 正确，对于正常二叉树，空指针域数量是 n+1 个，再讨论本题三叉链表引入的父亲指针，只有根结点没有父亲结点，所以多出来一个空指针域，因此总的空指针域是 n+2 个。II 错误，比如一棵高度为 h 的二叉树，根节点左子树高度为 h-1，那么根结点的右孩子的前驱结点是根节点左子树里的先序序列最后一个结点，这个结点一定在最底层，所以最坏结果，时间开销是 O（h）。III 正确，叶子结点没有孩子结点，所以指向他的结点只有他的父亲节点，但要注意根节点是叶子结点的例外，这里题目说了 n>1，所以不存在根节点是叶子结点的情况，因此该选项正确。IV 错误，度为 2 的分支结点可能是根节点，根节点的双亲指针为空。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
速对表原值： C
详细解析标注： C
先序序列是…a…b...，则 b 在 a 的左子树中或者 b 在 a 的某个祖先 x 的右子树中，中序序列是…b…a…，则 b 不可在 a 的某个祖先 x 的右子树中，即 b 只能在 a 的左子树中。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
速对表原值： C
详细解析标注： C
二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针链走到底的结点，设用 p 指示。若结点 p 不是叶结点(其左子树非空)，则前序遍历的最后一个结点在它的左子树中，A、B错误：若结点 p 是叶结点，则前序与中序遍历的最后一个结点就是它，C 正确。若中序遍历的最后一个结点 p 不是叶结点，它还有一个左子女 q，结点 q 是叶结点，那么结点 q 是前序遍历的最后一个结点，但不是中序遍历的最后一个结点，D 错误。
Q21¶
速对表原值： D
详细解析标注： D
后序遍历的顺序是 LRN，若 n 在 N 的左子树，m 在 N 的右子树，则在后序遍历的过程中 n 在 m 之前访问；若 n 是 m 的子孙，设 m 在 N 的位置，则 n 无论是在 m 的左子树还是在右子树，在后序遍历的过程中 n 都在 m 之前访问。其他都不可以。选项 C 要成立，就需加上两个结点位于同一层这个条件。
Q22¶
速对表原值： B
详细解析标注： B
首先观察先序和中序的非递归代码，可以发现，先序序列是在入栈的时候输出元素，中序序列是在出栈的时候输出元素，其他代码都一致。即得出：先序等价于入栈序列，中序等价于出栈序列。入栈序列可以通过卡特兰数推出栈序列个数。先序+中序可以确定一棵唯一的二叉树，先序确定，中序序列的不同个数是卡特兰数，所以二叉树的树型即卡特兰数种。n=4 的卡特兰数是〔公式/符号见原页版面片段〕 4 =〔公式/符号见原页版面片段〕2∗4 4 4+1 = 14。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
速对表原值： B
详细解析标注： B
原题同上题，由于二叉排序树（BST）中序是升序序列，n 个不同的元素组成的二叉排序树，中序序列唯一。确定中序序列（出栈序列），可以推不同的先序序列个数（入栈序列）是卡特兰数种，再由先序+中序确定一棵唯一的二叉树可以得到，不同的二叉树树型是 n=4 的卡特兰数14，答案为 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
速对表原值： C
详细解析标注： C
通过中序遍历即可得到正确的算术表达式，注意，每读出一个操作符，都需要在对应位置加上括号：(((A * B)+C)) / ((D * E)+(F - G)))。再根据无意义的括号合理删减，找出选项中与之匹配的正确答案。答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
速对表原值： C
详细解析标注： C
在后序遍历退回时访问根结点，就可以从下向上把从 n 到 m 的路径上的结点输出，若采用非递归的算法，则当后序遍历访问到 n 时，栈中把从根到 n 的父指针的路径上的结点都记忆下来，也可以找到从 m 到 n 的路径。
Q26¶
速对表原值： D
详细解析标注： D
Ⅰ错误，树的层序遍历一般使用队列。
Ⅱ正确，图的深度优先遍历必须使用栈。
Ⅲ错误，图的广度优先遍历一般使用队列。
Ⅳ正确，见上一题解析。
Q27¶
速对表原值： B
详细解析标注： B
只要按照前序序列的顺序入栈，无论怎么出栈肯定是符合中序序列的，所以这个问题就变成了，如果给定一个栈，入栈顺序是 ABCDEFG，那么下面哪种出栈顺序是可能的。只有 B 选项可以满足。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
速对表原值： A
详细解析标注： A
中序遍历和后序遍历能唯一确定一棵树，能画出一棵树即符合，只有 A 不符合，其他三个选项树的结构如下：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
速对表原值： C
详细解析标注： C
二叉树的前序序列为 ABCDEFG，A 为根节点。中序序列为 DCBAEFG，可知DCB 为左子树节点，EFG 为右子树节点。同理 B 为 C 父节点，C 为 D 父节点。同理 E 为 F 根节点，F为 G 根节点。故二叉树深度为 4 层。
C 选项正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
速对表原值： D
详细解析标注： D
由中序序列和层序序列可以唯一确定一棵二叉树，对于层序序列，可以确定子树的根节点，在中序序列中的左右位置可以确定这个节点是左子树还是右子树的根结点，由此直到遍历完整个序列。二叉树如下图所示，可知正确答案是 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q31¶
速对表原值： C
详细解析标注： C
二叉排序树的中序遍历为有序序列 10.15.20.23.25.30.35.39.42。而题目给出了后序遍 历 序 列 15.10, 23.25.20.35.42.39.30 。 因 此 可 以 构 建 唯 一 一 棵 二 叉 树 ， 前 序 遍 历 为30.20.10.15.25.23.39.35.42。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q32¶
速对表原值： A
详细解析标注： A
Ⅰ错误，任一二叉树的叶结点在先序、中序、后序遍历序列中相对位置一定是相同的。
Ⅱ错误，要交换二叉树的所有分支结点的左右子树的位置，利用前序或后序遍历框架解决最合适，只要保证先处理好左右子树，再处理根结点的思路就行。
Ⅲ正确，含有 n 个结点的二叉树最多有〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1种形态。
Ⅳ正确，NLR 和 LNR 顺序相反，说明对于每一层的 L，N，R，中 L 为空或 R 为空，得到的树的结果就是该二叉树仅有一个叶子结点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q33¶
速对表原值： B
详细解析标注： B
三种遍历分别是“根左右”，“左根右”，“左右根”，所以只有分支结点之间顺序有差异，叶子节点都是从左到右按顺序排放的。
Q34¶
速对表原值： D
详细解析标注： D
由题可知，该二叉树只可能是左单链或右单链，故答案选 D。
Q35¶
速对表原值： B
详细解析标注： B
中序是“左根右”，后序是“左右根”，因为根（分支结点）是不可或缺的。所以考虑减去左子树或者右子树保证他们是一致的。如果没有左子树，那么中序是“根右”，后序是“右根”，两个相反；没有右子树，中序是“左根”，后序也是“左根”
Q36¶
速对表原值： A
详细解析标注： A
元素个数确定，完全二叉树的树型也是确定，可以知道是一棵高度为 3 的满二叉树，再按中序遍历将元素值依次填到各个结点，然后写出先序序列，可以知道答案为 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
速对表原值： D
详细解析标注： D
首先分析根结点孩子的情况，因为先序序列是 a，e，后序结尾是 e，a，那么有几种情况：
①若根结点有左孩子。那么 e 一定是左孩子，且一定没有右孩子（否则右孩子结点后序一定夹在 e，a 之间，不符合题意）
②若根节点没有左孩子。那么 e 一定是右孩子。因此根节点只有一个孩子，A 选项正确。既然根只有一个孩子，那么可以不考虑根 a 了，只考虑以 e 为根的子树。先序为 e, b, d, c，后序是b, c, d, e，可以观察在先序中，b 在 e 后面，那么只可能 b 为 e 的左孩子（反证法：如果 b 是右孩子，那么由前序 e，b 相邻可推一定没有左子树，但是后序结尾一定是 b，e，但题目是 d，e，可知此情况不符合题意）。由于后序中 b 在最前面，所以 b 一定没有孩子（那么 e 的左子树只有 b 一个结点）。最后只剩一下一个结点 c 了，可知 c 在 d 的左右皆可。综上，B 正确，该度为 2 的结点为 e。
C 正确。D 选择，c 在 d 左右皆可。由上面分析，此题有 4 种树型，e 居 a 左右皆可（2 种），c 在 d 左右皆可（2 种），两者独立，所以总树型 2*2=4。大家看到这里应该也能很轻松画出来。这题是真题改编，做到这里也算把这道题目研究到位了，希望大家体会这种逐帧分析的思维过程。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q38¶
速对表原值： D
详细解析标注： D
A 正确：前序与中序一致 → 无左子树，每次直接访问根，再遍历右子树。
B 正确：后序与中序一致 → 无右子树，遍历完左子树直接访问根。
C 正确：单节点二叉树（仅有根，无左右孩子），三种遍历序列完全相同。
D 错误：任意一棵二叉树的所有叶子节点，在三种遍历中都遵循先左后右，相对顺序永远不变，这是重要推论。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q39¶
速对表原值： C
详细解析标注： C
先序遍历(根、左、右)：首先访问根结点，然后遍历左子树，最后遍历右子树。后序遍历(左、右、根)：首先遍历左子树，然后遍历右子树，最后访问根结点。假设存在一个结点 z 把x、y 分居 z 两侧，由先序遍历可知，x 在 z 的左子树，y 在 z 的右子树，那么在后序遍历中，x 一定也在y 前面，与题意不符。因此不存在这样的 z，即 x、y 一定同时是根节点到他们各自的路径上的中间结点，即 x 是 y 的祖先。
Q40¶
速对表原值： C
详细解析标注： C
当 5 出队的时候，此时队列里面有 6、7、8、9、10、11 一共 6 个元素，所以队列空间的最小值是 6。
Q41¶
速对表原值： B
详细解析标注： B
A 错误，树的遍历中，没有中序遍历的概念；对于 B，树转换为二叉树时，结点的左孩子是它在树中的第一个孩子，右孩子是它在树中的兄弟，而根结点不存在兄弟结点的概念，必然没有右子树；
C 错误，树的先序遍历就是相应二叉树的先序遍历；
D 错误，当树中的叶结点有兄弟结点时，转换后它就有右孩子了，而不再是叶子结点。
Q42¶
速对表原值： B
详细解析标注： B
完全二叉树中度为 1 的结点数为 0 或 1。当 n1=0 时，有 n2=n, no=n+1，共 2(n+1)个空指针作线索。当 n1=1 时，有 n2=n-1, no=n，共 2n+1 个空指针作线索。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q43¶
速对表原值： C
详细解析标注： C
根据线索二叉树的定义，rtag=0 表示有右孩子，rtag=1 表示没有有孩子，右指针表示的是后继的线索。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q44¶
速对表原值： C
详细解析标注： C
中序+后序可以确定一棵唯一的二叉树，如下图所示，右孩子为空的结点在线索二叉树中，右孩子指针指向线索。由图可知有 CDA 三个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q45¶
速对表原值： D
详细解析标注： D
D 选项错误，若该非根结点是其父亲结点的左孩子，且存在右孩子，那么右指针一定指向右孩子所在子树后序遍历的第一个结点。
B 正确，先序线索二叉树可能无法直接找到前驱，后序线索二叉树可能无法直接找到后继，需要通过从头遍历或者三叉链表（多一个指针指向父亲结点）找到。
Q46¶
速对表原值： D
详细解析标注： D
后序线索二叉树不能有效解决求后序后继的问题。如下图所示，结点 E 的右指针指向右孩子，而在后序序列中 E 的后继结点为 B，在查找 E 的后继时仍然只能按常规方法来查找。
注意：先序线索二叉树中求前驱也是不能有效求解
原页版面片段（用于核对图表、公式、矩阵或代码）
Q47¶
速对表原值： B
详细解析标注： B
后序遍历序列为 f、d、e、b、c、a，左右线索分别指向 c 的后序前驱 b 和后继 a，因此答案选 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q48¶
速对表原值： C
详细解析标注： C
先序线索二叉树的缺点：无法找到先序序列中某结点的前驱；后序线索二叉树的缺点：无法找到后序序列中某结点的后继。如图，后序线索树只能找前驱，6 的后继为 7，但 6 的两个指针域中一个指向了它的前驱 5，一个指向了 4，故无法找到其后继，需要借助其他工具（如栈）帮助完成。中序线索二叉树 先序线索二叉树 后序线索二叉树找前驱 √ x √找后继 √ √ x
原页版面片段（用于核对图表、公式、矩阵或代码）
Q49¶
速对表原值： C
详细解析标注： C
A 正确，该结点的中序后继结点是它的右子树的最左边的结点，所以它没有左孩子。它的中序前驱结点是它的左子树的最右边的结点，所以它没有右孩子。
B 正确，可以通过具体的例子来验证该结论。
C 错误，中序线索二叉树当右孩子为空可以通过右线索直接找到后继，如果右孩子不为空，也可以找到中序后继（通过右孩子找到右子树中最左的结点），因此可以完成中序遍历。
D 正确，因为 x 是一个根结点，x 要么是 y 的右孩子（y 在 x 的左边，y 的数值比 x 的小），要么是 y 的右孩子（y 在 x 的右边，y 的数值比 x 的大），又因为 x 没有左子树和右子树，所以 y 即是 x 的前驱或后继的结点。即 y 的数值要么是树中大于 x 的数值的最小关键字，要么是树中小于 x，数值的最大关键字。
Q50¶
速对表原值： A
详细解析标注： A
B：如果仅有右孩子，则中序形式为：根、右，此时后继节点存在。C：先序与后序的形式分别是根、左、右和左、右、根，根据这两种遍历序列的信息无法区分左、右子树。D：通常有左子树而无右子树。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q51¶
速对表原值： B
详细解析标注： B
在树的孩子兄弟表示法中，若一个结点没有孩子(即叶结点)，则表现为该结点的左指针域为空，因此本题答案为“6”。至于“5 个结点的左、右指针域都为空”，表示树中有 5 个结点既没有孩子又没有兄弟，约束条件比题中的“求叶结点的个数”要求更严格。
Q52¶
速对表原值： D
详细解析标注： D
A 正确，原森林中每一个分支结点产生唯一一个对应二叉树中没有右孩子的结点，且这个结点是原森林中这个分支节点最右边的孩子（左孩子右兄弟，最右边的孩子没有右兄弟，所以对应二叉树中右指针为空），森林中最右边子树的根节点在二叉树中也没有右孩子，这 1 个是特殊的。由此可以知道原森林中分支节点个数+1=二叉树中没有右孩子的节点数量。
B 正确，森林左孩子右兄弟转换中，在二叉树中只有每棵树的根节点相连接的分支是比原森林多出来，所以当树为 1 棵时，没有多余的分支多出。
C 正确，“左孩子右兄弟”，二叉树中没有左孩子的结点即原森林中的叶子节点。
D 错误，若二叉树中该结点是根节点，那么它的左右孩子不存在亲缘关系。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q53¶
速对表原值： B
详细解析标注： B
F 的先根遍历对应 T 的先序遍历，所以画出 T 的图即可得到答案为 B。
Q54¶
速对表原值： D
详细解析标注： D
二叉排序树的中序遍历为有序序列 10, 15, 20, 23, 25, 30, 35, 39, 42。二叉树转换的森林的后根遍历对应二叉树的中序遍历，故答案为 D。也可尝试层序+中序构造一棵二叉树可知 B 为先序，C 为后序，不过稍显复杂。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q55¶
速对表原值： B
详细解析标注： B
树和森林的遍历与二叉树遍历的对应关系树 森林 二叉树先根遍历 先序遍历 先序遍历后根遍历 中序遍历 中序遍历
Q56¶
速对表原值： B
详细解析标注： B
该树至少有两个节点，对于有两个或两个以上节点的树，至少有两个节点没有右兄弟(根节点和其最右孩子节点)，而右指针域指向兄弟节点。所以本题答案为 B。
Q57¶
速对表原值： D
详细解析标注： D
画出图像如右发现根结点一直向右走直到叶结点的路径上，共有 3 个结点，所以森林中一共有 4 棵树，其中最大的那棵树是森林的第 1 棵树，共有 9 个结点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q58¶
速对表原值： D
详细解析标注： D
将森林转换成二叉树方法是“左孩子右兄弟”。森林中每棵树都相互独立，可将每棵树的根结点全部视作兄弟。题目内的森林转换后，树 2 作为树 1 的根结点的右子树，树 3 作为树 2的根结点的右子树。森林 F 对应二叉树根结点的右子树上的结点个数是 M_{2} + M_{3}。
Q59¶
速对表原值： C
详细解析标注： C
每个指向双亲的指针都对应树中的一个分支，含有 n 个结点的树中最少有 n - 1 个分支。
Q60¶
速对表原值： D
详细解析标注： D
A 正确，森林中有多少棵树，要看根节点开始往右遍历一共有多少个结点，高 h的满二叉树有 h 个，所以有 h 棵树。
B 正确，原森林中每一个分支结点产生唯一一个对应二叉树中没有右孩子的结点，且这个结点是原森林中这个分支节点最右边的孩子（左孩子右兄弟，最右边的孩子没有兄弟，所以对应二叉树中右指针为空），森林中最右边子树的根节点本身也没有右孩子，这个是特殊的，由此可以知道原森林中分支节点个数+1=二叉树中没有右孩子的节点数量。满二叉树没有右孩子的节点数量即最后一排的叶子节点2ℎ−1个，减去 1 即为原森林中的分支结点数。
C 正确，第 i 棵树对应的二叉树中的部分是根（根为第 1 个）的第 i 个右分支作为根节点，加上一个高度为 h-i 的满二叉树，所以总结点个数是2ℎ−〔公式/符号见原页版面片段〕 − 1 + 1 = 2ℎ−〔公式/符号见原页版面片段〕个D 错误，第 i 棵树的二叉树部分见 C 选项解释，易知度最大的结点是二叉树中根节点的孩子结点。该结点在二叉树中往右一直遍历有 h-i 个结点（包括自己），即有 h-i-1 个右兄弟，所以度最大的结点为根结点，最大为 h-i。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q61¶
速对表原值： B
详细解析标注： B
树可以通过孩子兄弟表示法转换成唯一一棵二叉树，所以本题转换成求对应的二叉树的树型有多少种。我们首先分析转化得到的二叉树树型特点，由于树的根节点没有兄弟结点，所以在转换的二叉树中，根节点没有右兄弟，即除根节点之外的 3 个结点构成一棵左子树。这个左子树的树型数目就是我们要求的答案。3 个结点的二叉树不同树型可用卡特兰数来求，〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1代入 n=3 求得答案为 5。卡特兰数的题型总结：
-
入栈序列为 12...n 的出栈序列个数？证 明 方 法 一 ： 利 用 卡 特 兰 数 的 递 推 式 ： 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 0 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 − 2 + ... + 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 0 =〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1当元素 1 放在出栈序列第 k 个位置时，前面 k-1 个位置一定是 2～k 共计 k-1 个元素的出栈排列个数H(k-1)，右边位置是 k+1～n 共计 n-k 个元素的出栈序列排列个数 H(n-k)，由此得到上述递推式。证明方法二：网格法，〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕−1入栈操作为横坐标，出栈操作为纵坐标，n 次入栈+n 次出栈操作即从原点出发到(n,n)的路径个数，即 2n 次操作里面选择 n 次入栈（剩下的是出栈）的可能数，即〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕，但是每个时刻，出栈次数不能比入栈次数多，否则就是不合法。如下图，我们可以知道，不合法的操作路径，一定会触碰 y=x+1 到达(n, n)，而这样的路径经过 y=x+1 反射都会到达点（n-1, n+1），所以所有不合法的路径即从原点出发到点(n-1, n+1)的所有路径数量。综合以上，合法操作路径条数=〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕−1 =〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1（只要触碰到 y=x+1 说明当前状态出栈比入栈次数多，非法序列），
-
出栈序列为 12...n 的入栈序列个数？逆向思维，根据上述网格法，其实合法序列就是不同的路径的条数，每一条路径的出栈出栈次序有差异，得到的出栈序列也有差异，那么我们固定出栈序列，通过路径还原成入栈序列，肯定也是不同的。所以结果还是卡特兰数。
-
n 个结点二叉树的树型有多少种？证明：利用卡特兰数的递推式：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 0 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 − 2 + ... + 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 0思想：确定根节点后，剩余 n-1 个结点各自分配在左右子树，形成以上卡特兰数的递推数学模型。
-
进一步，结合树和二叉树的转换（左孩子右兄弟）：含有 n 个结点的树的有多少种形态 （n-1的卡特兰数）
-
结合森林和二叉树的转换（左孩子右兄弟）：含有 n 个结点的森林的有多少种形态 （n 的卡特兰数）
-
结合二叉树先序中序： 给定先序序列（n 个值不同）的不同二叉树的个数 n 个不同权值的结点的二叉排序树的个数（中序确定）首先观察先序和中序的非递归代码，可以发现，先序序列是在入栈的时候输出元素，中序序列是在出栈的时候输出元素，其他代码都一致。即得出：先序等价于入栈序列，中序等价于出栈序列。入栈序列可以通过卡特兰数推出栈序列个数。先序+中序可以确定一棵唯一的二叉树，先序确定，中序序列的不同个数是卡特兰数，所以二叉树的树型即卡特兰数种。n=4 的卡特兰数是〔公式/符号见原页版面片段〕 4 =〔公式/符号见原页版面片段〕2∗4 4 4+1 = 14。
-
n 对括号的不同排列个数：证明可以用坐标路径法。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q62¶
速对表原值： D
详细解析标注： D
原森林的先根遍历是二叉树的先序遍历为 5, 2, 1, 4, 3, 6, 10, 8, 7, 9。
Q63¶
速对表原值： C
详细解析标注： C
中序+后序可以确定一棵唯一的二叉树。该二叉树如右图：该二叉树对应的森林，树的个数即根结点到最右边叶子节点路径上的结点个数，即 A、C、F 三个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q64¶
速对表原值： A
详细解析标注： A
T1，T2，T3 先分别转化为二叉树，除掉根结点，其它结点都转化为根结点的左孩子，第一棵二叉树不动，后面的二叉树分别是前面二叉树的右孩子。故本题中 T1 不动，左孩子结点N1-1。
Q65¶
速对表原值： D
详细解析标注： D
D：通过只有 3 个节点（其中 a 为根节点，b 为 a 的左孩子，c 为 b 的右孩子）的二叉树来验证本叙述是不正确的。C：当二叉树只有一个根节点时，任何遍历的序列均相同。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q66¶
速对表原值： C
详细解析标注： C
I 错误，比如 3 个结点构成的链；II、III 正确；IV 错误，3214 和 3421 和 3241 构成的 BST 都是一致的；V 错误，比如只有一个根节点。
Q67¶
速对表原值： D
详细解析标注： D
在一组哈夫曼编码中，哈夫曼树中只有度为 0 或 2 的节点，D 不满足这种条件。
Q68¶
速对表原值： A
详细解析标注： A
首先排除不满足前缀特性的选项，易知 B 选项出现 00 是 000 的前缀，排除。C 选项，10 是 1011 的前缀，排除。此时还剩 A，D。接着根据频次越高，编码越短的特性。A，D 选项第一个和第二个编码长度刚好是相反的，第一个频次是 6，第二个频次是 3，所以第一个编码必然比第二个短，所以答案选 A。这道题是真题，大家应该学会这种不画图的解法，多利用某些数据结构的性质。
Q69¶
速对表原值： C
详细解析标注： C
A 错误，对于题目中的场景，使用哈夫曼编码对应的哈夫曼树是一棵满二叉树。因为从最底层开始，最底层是两两配对的，根据题意对任一频率 〔公式/符号见原页版面片段〕 有 〔公式/符号见原页版面片段〕 ≤ 〔公式/符号见原页版面片段〕 < 2〔公式/符号见原页版面片段〕，所以没有任何一对的频率超过另外一对的 2 倍，进而得出没有任何一个内部结点的频率是同一层的内部结点频率的两倍，所以该哈夫曼树是一个满二叉树。对于编码相应的前缀树是满二叉树情形，没有更优的编码方式了。
B 错误，哈夫曼树中不存在度为 1 的结点。
C 正确，哈夫曼树中 〔公式/符号见原页版面片段〕1 = 0, 〔公式/符号见原页版面片段〕2 = 〔公式/符号见原页版面片段〕0 − 1，那么总的结点数目 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕0 + 〔公式/符号见原页版面片段〕2 = 2〔公式/符号见原页版面片段〕0 − 1，它是一个奇数。
D错误，对于权值都是正数的结点构成的哈夫曼树，父结点的权值一定是大于它的孩子结点的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q70¶
速对表原值： D
详细解析标注： D
初始森林中的 n 棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子。n 个叶子的哈夫曼树要经过 n-1 次合并，产生 n-1 个新结点。
Q71¶
速对表原值： A
详细解析标注： A
题目里要求左节点的值小于右节点的值，所以构造下图所示的哈夫曼树：一棵哈夫曼树的带权路径长度等于树中所有的叶结点的权值乘上其到根结点的路径长度。所以长度：（2+3）* 4+（4+6+7）* 3+15 *1=86，B 的编码（也就是 3）为 1011。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q72¶
速对表原值： B
详细解析标注： B
A 不符合，可以知道，16+10=26，也就是第二层是符合的。但是第三层，16=5+11，10=6+4，4，5 更小，应该优先合并，而不是 4 跟 6 合并，不合符哈夫曼树最优二叉树的性质，因此错误。B 选择正确。
C 选项错误，26≠10+12，第二层出错。
D 选项错误，16≠7+8，第三层出错。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q73¶
速对表原值： A
详细解析标注： A
A 正确，带全路径长度 WPL 是每个叶节点的带权路径长度之和；
B 错误，哈夫曼树只有度为 2 和 0 的结点，并不一定是完全二叉树。
C 错误，度为 2 的有序树不可以是空树，但是二叉树可以。
D 错误，BST 不同于 AVL，删除分支结点一定要找一个前驱或后继来代替，而重新插入这个结点，一定在叶子结点，导致树形发生改变；同样地，删除叶子结点再插入是一定一样的。而 AVL 中，删除分支结点在插入，树形可能不改变，比如 123 依次插入，删除 2 再插入 2，树不改变。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q74¶
速对表原值： C
详细解析标注： C
度为 m 的哈夫曼树中，只有度为 m 和叶子结点，由公式：度数之和+1=结点总数可以得到，〔公式/符号见原页版面片段〕 + 1 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕0 → 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕0 − 1 → 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 − 1 / 〔公式/符号见原页版面片段〕 − 1 ，但我们要注意到，度为 m 的哈夫曼树，当 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 = 0，不需要补充虚结点；当 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 ≠ 0，我们要补充虚结点，补充的虚结点个数为 〔公式/符号见原页版面片段〕 − 1 − 〔公式/符号见原页版面片段〕 − 1 % 〔公式/符号见原页版面片段〕 − 1 。〔公式/符号见原页版面片段〕是整数，实际上加上虚结点的叶结点数是>=n 的，所以要取上整。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q75¶
速对表原值： C
详细解析标注： C
初始时，0～9 各自成一个集合。査找 1-2 时，合并{1}和{2}；查找 3-4 时，合并{3}和{4}；查找 5-6 时，合并{5}和{6}；査找 7-8 时，合并{7}和{8}；査找 8-9 时，合并{7, 8}和{9}；查找 1-8 时，合并{1, 2)和{7, 8, 9}；査找 0-5 时，合并{0}和{5, 6}；查找 1-9 时，它们属于同一个集合。最终的集合为{0, 5, 6}、{1, 2, 7, 8, 9}和{3, 4}，因此答案选择选项 C。
Q76¶
速对表原值： D
详细解析标注： D
依次探测图的各条边，用并查集检查该边依附的两个顶点是否已属于同一集合(两个顶点的根结点是否相同)。若是，则说明图中存在环路，A 错误。经过路径优化后，并查集在最坏情况下的高度远小于 O(n)，B 错误。Find 操作返回的是集合根结点的下标，元素个数的相反数是 P[根的下标]，C 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q77¶
速对表原值： D
详细解析标注： D
在用并查集实现 Kruskal 算法求图的最小生成树时：判断是否加入一条边之前，先查找这条边关联的两个顶点是否属于同一个集合(即判断加入这条边之后是否形成回路)，若形成回路，则继续判断下一条边：若不形成回路，则将该边和边对应的顶点加入最小生成树 T，并继续判断下一条边，直到所有顶点都已加入最小生成树 T。
B 正确。用并查集判断无向图连通性的方法：遍历无向图的边，每遍历到一条边，就把这条边连接的两个顶点合并到同一个集合中，处理完所有边后，只要是相互连通的顶点都会被合并到同一个子集合中，相互不连通的顶点一定在不同的子集合中。
C 正确。未做路径优化的并查集在最坏情况下的高度为n，此时查找操作的时间复杂度为O（n），时间复杂度通常指最坏情况下的时间复杂度。
D 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q78¶
速对表原值： D
详细解析标注： D
III 错误，返回的是根节点 root 的编号(大于 0)，而不是 S[root]（小于 0）。IV 错误，Union()操作始终都是 O(1)，改进是小树合并到大树，的目是降低整个集合树的高度至〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 。V 错误，Find()经过压缩路径优化后，可使集合树的深度为〔公式/符号见原页版面片段〕 ，〔公式/符号见原页版面片段〕 是一个接近常数的函数。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q79¶
速对表原值： D
详细解析标注： D
得到的并查集如图所示，要注意最后一个 Union 要路径压缩，parent[8]=5，parent[4]=1，因为属于一个集合，所以 find(任意结点)=1。只有 D 正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q80¶
速对表原值： B
详细解析标注： B
I 正确，BT 根结点一直往右遍历可以得到 k 个结点，那么 F 一定有 k 棵树，森林中，边+树棵树=结点个数，所以 F 中边数=n-k。II 正确，F 中任意一个分支结点，根据左孩子右兄弟，最靠右的孩子结点在对应二叉树中一定没有右指针。根节点是特殊的一个，在森林中，最右边那棵树的根节点一定没有右孩子，所以一共有 m+1 个空右指针的结点。III 正确，根据左孩子右兄弟，F 中没有左孩子，在原森林中一定是叶子结点（没有孩子）。所以二者是相等关系。IV 错误，也有可能是 h-1 棵树。只有满二叉树的情况下，一定保证是 h 棵树。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q81¶
速对表原值： B
详细解析标注： B
哈夫曼编码的加权平均长度是 wpl/总频次。构造的哈夫曼树如下图所示，wpl=(3+4+5+6)*2=36，所以加权平均长度=36/(3+4+5+6)=2。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q82¶
速对表原值： D
详细解析标注： D
分四种情况如下图所示。在树中：第一种情况，u 是 v 的爷爷的兄弟。第二种情况，u 是 v 的叔叔（A 选项），第三种情况，u 和 v 有共同爷爷（B 选项）。第四种情况，v 是 u 的叔叔（C 选项）。
原页版面片段（用于核对图表、公式、矩阵或代码）
