5.3.4 答案与解析
## 5.3.4 答案与解析 ### 一、单项选择题 #### 01. C 二叉树中序遍历的最后一个结点一定是从根开始沿右孩子指针链走到底的结点，设用 $p$ 指示。若结点 $p$ 不是叶结点（其左子树非空），则先序遍历的最后一个结点在它的左子树中，选项A、B错误；若结点 $p$ 是叶结点，则先序与中序遍历的最后一个结点就是它，选项C正确。若中序遍历的最后一个结点 $p$ 不是叶结点，它还有一个左孩子 $q$，结点 $q$ 是叶结点，那么结点 $q$ 是先序遍历的最后一个结点，但不是中序遍历的最后一个结点，选项D错误。 #### 02. C 三种遍历方式中，都先遍历左子树，再遍历右子树，因此 $b$ 一定在 $c$ 的前面访问。 #### 03. C 中序遍历时，先访问左子树，再访问根结点，后访问右子树。$n$ 在 $m$ 前的3种可能性如右图所示，从中看出 $n$ 总是在 $m$ 的左方。 【另解】设 $n$ 和 $m$ 的最近公共祖先 $p$，则有以下可能： 情形1，$m$ 和 $n$ 分别在 $p$ 的左右（右左）分支上；情形2，$m$ 或 $n$ 为 $p$ 结点，另一结点在 $p$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) <!-- page: 165 --> 第5章 树与二叉树 153 的分支上。只有 $n$ 和 $m$ 分别处于 $p$ 的左右分支上，$m$ 为祖先结点且 $n$ 位于 $m$ 的左分支，$n$ 为祖先结点且 $m$ 位于 $n$ 的右分支，符合题意。 04. D 后序遍历的顺序是 LRN，若 $n$ 在 N 的左子树上，$m$ 在 N 的右子树上，则在后序遍历的过程中 $n$ 在 $m$ 之前访问；若 $n$ 是 $m$ 的子孙，设 $m$ 在 N 的位置，则 $n$ 无论是在 $m$ 的左子树还是在右子树，在后序遍历的过程中 $n$ 都在 $m$ 之前访问。其他都不可以。选项 C 要成立，就需加上两个结点位于同一层这个条件。 05. C 在二叉树的数组存储结构中，下标为 $i$ 的结点的左右孩子的下标分别为 $2i + 1$ 和 $2i + 2$（若存在），画出二叉树的形态如下右图所示，则后序遍历序列为 gdbhefca。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
06. B 三种遍历方式中，访问左右子树的先后顺序是不变的，只是访问根结点的顺序不同，因此叶结点的先后顺序完全相同。此外，读者可以采用特殊值法，画一个结点数为 3 的满二叉树，采用三种遍历方式来验证答案的正确性。 07. C 对每个顶点从 1 开始按序编号，要求结点编号大于其左右孩子编号，并且左孩子编号小于右孩子编号。编号越大说明遍历顺序越靠后，因此，三者遍历顺序为先左子树、再右子树、后根结点。4 个选项中仅后序遍历满足要求。 08. B 结点 $\nu$ 的编号比其左子树上的最小编号还小，而 $\nu$ 的右子树中的最小编号大于 $\nu$ 的左子树中的最大编号，因此 $\nu$ 的编号比其左右子树上的所有编号都小，显然是按先序遍历次序。 09. D 先序为 $A$、$B$、$C$ 的不同二叉树共有 5 种，其中后序为 $C$、$B$、$A$ 的有 4 种（前 4 种），都是单支树，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
10. C 7 个结点的完全二叉树是一棵 3 层的满二叉树，画出相应二叉树的树形，根据后序遍历序列填入相应的结点，得到相应的完全二叉树，求得其先序遍历序列为 $ABCDEFG$。 11. C 二叉树的先序遍历为 NLR，后序遍历为 LRN。根据题意，在先序序列中 $X$ 在 $Y$ 之前，在后序序列中 $X$ 在 $Y$ 之后，若设 $X$ 在根的位置，$Y$ 在其左子树或右子树中，即满足要求。 12. C 先序序列是 $\dots a\dots b\dots$，因此 $a$ 和 $b$ 结点的 3 种情况如下图(a)~(c)所示。中序序列是 $\dots b\dots a\dots$，因此 $a$ 和 $b$ 结点的 3 种情况如下图(d)~(f)所示，相同部分是 $b$ 在 $a$ 的左子树中。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(e)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(f) <!-- page: 166 --> 2027年数据结构考研复习指导 13. B 解法1：由题可知，1为根结点，2为1的孩子。对于选项A，3应为1的左孩子，先序序列应为13…，不符题意。类似地，选项C也是错误的。对于选项B，2为1的右孩子，3为2的右孩子……满足题意。对于选项D，463572应为1的右子树，2为1的右孩子，46357为2的左子树，3为2的左孩子，46为3的左子树，57为3的右子树，先序序列4、6应相连，5、7应相连，不符题意。 解法2：先序遍历时需要借助栈。二叉树的先序序列和中序序列的关系相当于以先序序列作为入栈次序，以中序序列作为出栈次序。题中以1234567入栈；对于选项A，第一个出栈的是3，所以1不可能在2之前出栈，错误。对于选项C，1不可能在3之前出栈，错误。对于选项D，6第三个出栈，此时栈顶元素是5，不是3，错误。选项B正确。 解法3：因先序序列和中序序列可以确定一棵二叉树，所以可试着用题目中的序列构造出相应的二叉树，即可得知，只有选项B的序列可以构造出二叉树。 14. D 先序序列为NLR，后序序列为LRN，虽然可以唯一确定树的根结点，但无法划分左右子树。例如，先序序列为 $AB$ ，后序序列为 $BA$ ，则其对应的二叉树如右图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
15. B 中序遍历是“左根右”，后序遍历是“左右根”，当任一结点没有右子树时，两种遍历都是“左根”。显然，当二叉树为空树或只有根结点时，其中序序列和后序序列也相同。 16. D 根据后序序列与中序序列可构造出二叉树，如下图所示。由图可知先序序列为CEDBA。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 确定根结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 确定左子树根结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 确定剩下的子树 17. A 对于这种遍历序列问题，先根据遍历的性质排除若干项，若还无法确定答案，则再根据遍历结果得到二叉树，找到对应遍历序列。例如，在本题中，已知先序和中序遍历结果，可知本树的根结点为 $A$ ，左子树有 $C$ 和 $B$ ，其余为右子树，则后序遍历结果中， $A$ 一定在最后，并且 $C$ 和 $B$ 一定在前面，排除选项 $B$ 和 $D$ 。又因先序中有 $DEF$ ，中序中有 $EDF$ ，则 $D$ 为这个子树的根，所以 $D$ 在后序中排在 $EF$ 之后。 根据二叉树的递归定义，要确定二叉树，就要分别找到根结点和左右子树。因此，根据遍历结果，必定要确定根结点位置和如何划分左右子树，才可以确定最终的二叉树。因此，仅有先序和后序遍历不能唯一确定一棵二叉树，而二者之一加上中序遍历都可以唯一确定一棵二叉树。如在本题中，根据先序和中序遍历的结果确定二叉树的过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 确定根结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 确定左子树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 确定右子树 <!-- page: 167 --> 第5章 树与二叉树 155 18. B 可构造出二叉树如下图所示。因此，先序序列为 $ABCDEF$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 确定根结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 确定右子树的根结点
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 确定剩下的子树
19. B
先序遍历是根左右，祖先 $a$ 先于子孙 $b$ 访问，即 $\operatorname{pre}(a) < \operatorname{pre}(b)$，因此选项 A 一定成立。后序遍历是左右根，子孙 $b$ 先于祖先 $a$ 访问，即 $\operatorname{post}(b) < \operatorname{post}(a)$，因此选项 B 一定不成立。中序遍历是左根右，左子树中的子孙先于祖先访问，右子树中的子孙后于祖先访问，因此子孙的编号可能小于祖先的编号，也可能大于祖先的编号，选项 C 和 D 都有可能。
20. C
删除一个结点时，需要先递归地删除它的左右孩子，并释放它们所占的存储空间，然后删除该结点，并删除它所占的存储空间，这正好和后序遍历的访问顺序相吻合。
21. B
只要交换 $T$ 中所有分支结点的左右子树，就能得到一棵中序遍历序列为降序序列的树，而这并不会改变根结点，叶结点也仅仅交换位置，仍是原 $T$ 中的叶结点，选项 C、D 错误。交换 $T$ 中所有分支结点的左右子树，要么先处理根结点，然后递归地处理左右子树，即先序遍历；要么先处理左右子树，然后处理根结点，即后序遍历；中序遍历是不适合的。选项 A 错误，选项 B 正确。
22. A
线索是前驱结点和后继结点的指针，引入线索的目的是加快对二叉树的遍历。
23. C
$n$ 个结点共有链域指针 $2n$ 个，其中，除根结点外，每个结点都被一个指针指向。剩余的链域建立线索，共 $2n - (n - 1) = n + 1$ 个线索。
24. C
线索二叉树中用 ltag/rtag 标识结点的左/右指针域是否为线索，其值为 1 时，对应指针域为线索，其值为 0 时，对应指针域为左/右孩子。
25. D
对左子树为空的二叉树进行先序线索化，根结点的左子树为空并且也没有前驱结点（先遍历根结点），先序遍历的最后一个元素为叶结点，左右子树均为空且有前驱无后继结点，所以线索化后，树中空链域有 2 个。
26. D
不是每个结点通过线索都可以直接找到它的前驱和后继。在先序线索二叉树中查找一个结点的先序后继很简单，而查找先序前驱必须知道该结点的双亲结点。同样，在后序线索二叉树中查找一个结点的后序前驱也很简单，而查找后序后继也必须知道该结点的双亲结点，二叉链表中没有存放双亲的指针。
27. D
后序线索二叉树不能有效解决求后序后继的问题。如右图所示，结点 $E$ 的右指针指向右孩子，而在后序序列中 $E$ 的后继结点为 $B$，在查找
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 168 --> 2027年数据结构考研复习指导 $E$ 的后继时仍然只能按常规方法来查找。 28. C 在二叉中序线索树中，某结点若有左孩子，则按照中序“左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点（注意，并不一定是最右叶结点）。 29. A 在二叉树的后序遍历中，叶结点 $X$ 的后继是其双亲，因此 $X$ 的右线索应指向该结点。 30. B 非空二叉树的先序序列和后序序列相反，即“根左右”与“左右根”顺序相反，因此树只有根结点，或根结点只有左子树或右子树，其子树也有同样的性质，任意结点只有一个孩子，才能满足先序序列和后序序列正好相反。此时树形应为一个长链，树中仅有一个叶结点。 31. D 非空二叉树的先序序列和中序序列相反，即“根左右”与“左根右”顺序相反，因此树只有根结点，或任意一个结点只有左孩子，此时树形应该是一棵向左倾斜的单支树，这棵单支树只有一个叶结点。但是，只有一个叶结点的二叉树不能保证任意一个结点无右孩子。 32. D 分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是 RNL。本题考查的遍历方法并不是二叉树遍历的 3 种基本遍历方法，对于考生而言，重要的是掌握遍历的思想。 33. D 题中所给二叉树的后序序列为 $dbca$。结点 $d$ 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 $b$；结点 $b$ 无左子树，左链域指向其前驱结点 $d$；结点 $c$ 无左子树，左链域指向其前驱结点 $b$，无右子树，右链域指向其后继结点 $a$。 34. C 先序序列为 NLR，后序序列为 LRN，因为先序序列和后序序列刚好相反，所以不可能存在一个结点同时有左右孩子，即二叉树的高度为 4。1 为根结点，根结点只能有左孩子（或右孩子），因此在中序序列中，1 或在序列首或在序列尾，选项 A、B、C、D 皆满足要求。仅考虑以 1 的孩子结点 2 为根结点的子树，它也只能有左孩子（或右孩子），因此在中序序列中，2 或在序列首或在序列尾，选项 A、B、D 皆满足要求。 【另解】画出各选项与题干信息所对应的二叉树如下，所以选项 A、B、D 均满足。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
35. A 先序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系；当两个结点的先序序列为 $XY$ 与后序序列为 $YX$ 时，则 $X$ 为 $Y$ 的祖先。考虑先序序列 $a, e, b, d, c$、后序序列 $b, c, d, e, a$，可知 $a$ 为根结点，$e$ 为 $a$ 的孩子结点；此外，由 $a$ 的孩子结点的先序序列 $e, b, d, c$、后序序列 $b, c, d, e$，可知 $e$ 是 $bcd$ 的祖先，所以根结点的孩子结点只有 $e$。 <!-- page: 169 --> 第5章 树与二叉树 157
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d) 排除法：显然 $a$ 为根结点，且确定 $e$ 为 $a$ 的孩子结点，排除选项 D。各种遍历算法中左右子树的遍历次序是固定的，若 $b$ 也为 $a$ 的孩子结点，则在先序序列和后序序列中 $e$、$b$ 的相对次序应是不变的，所以排除选项 B，同理排除选项 C。 特殊法：先序序列和后序序列对应多棵不同的二叉树树形，我们只需画出满足该条件的任意一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。 显然选择选项 A，最终得到的二叉树满足题设中先序序列和后序序列的要求。 36. A。 根据后序线索二叉树的定义，$X$ 结点为叶结点且有左兄弟，因此这个结点为右孩子结点，利用后序遍历的方式可知 $X$ 结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如右所示的草图。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
37. D
线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列 debxac，中序遍历中在 $x$ 左边和右边的字符，就是它在中序线索化的左右线索，即 $b, a$。
38. B
根据二叉树先序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：先序序列和中序序列的关系相当于以先序序列为入栈次序，以中序序列为出栈次序。因为先序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 $a, b, c, d$ 为入栈次序，则出栈序列的个数为？”，对于 $n$ 个不同元素入栈，出栈序列的个数为 $\frac{1}{n+1} C_{2n}^{n} = 14$。
39. B
后序序列先访问左子树，接着访问右子树，最后访问父结点，递归进行。根结点左子树的叶结点首先被访问，它是 $e$。接下来是它的父结点 $a$，然后是 $a$ 的父结点 $c$。接着访问根结点的右子树。它的叶结点 $b$ 首先被访问，然后是 $b$ 的父结点 $d$，再后是 $d$ 的父结点 $g$，最后是根结点 $f$，如右图所示。因此 $d$ 与 $a$ 同层，选项 B 正确。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
40. B
先序序列先访问父结点，接着访问左子树，然后访问右子树。中序序列先访问左子树，接着访问父结点，然后访问右子树，递归进行。若所有非叶结点只有右子树，则先序序列和中序序列都先访问父结点，后访问右子树，递归进行。
41. B
对于此类题，每种情况只需举出一个反例即可。如图 1 所示，$q$ 是 $p$ 的双亲，中序遍历序列为 $\{p, q\}$，说法 I 可能。如图 2 所示，$q$ 是 $p$ 的右孩子，中序遍历序列为 $\{p, q\}$，说法 II 可能。如图 4 所示，$q$ 是 $p$ 的双亲的双亲，中序遍历序列为 $\{x, p, q\}$，说法 IV 可能。如图 3 所示，$q$ 是 $p$ 的右兄弟，$F$ 是 $q$ 和 $p$ 的父结点，中序遍历要求先遍历左子树，再访问根结点，最后遍历右子树，
<!-- page: 170 -->
2027年数据结构考研复习指导
因此一定先访问 $p$，再访问 $F$，最后访问 $q$，$p$ 和 $q$ 不可能相邻出现，说法 III 不可能。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图4 ## 42. A 根据二叉树的树形和后序遍历序列，可以轻松地将各字母填入结点中，如右图所示。 然后对该二叉树进行先序遍历，得到序列 $aedfbc$。 ## 43. A 根据中序遍历的特点，$\nu$ 有左右子树，以 $\nu$ 为根的子树的中序序列为：$\nu$ 的左子树的中序序列，$\nu, \nu$ 的右子树的中序序列。又因为 $T$ 的中序序列为“…，$p, \nu, q, \cdots$”，可知 $p$ 属于 $\nu$ 的左子树，$q$ 属于 $\nu$ 的右子树。在 $\nu$ 的左子树的中序序列中：假设 $p$ 有右孩子，则 $p$ 的右孩子在中序序列中应在 $p$ 之后，与 $p$ 是最后一个遍历结点矛盾，因此 $p$ 不存在右孩子。在 $\nu$ 的右子树的中序序列中：假设 $q$ 存在左孩子，则 $q$ 的左孩子在中序序列中应在 $q$ 之前，与 $q$ 是第一个遍历结点矛盾，因此 $q$ 不存在左孩子。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 二、综合应用题
### 01. 【解答】
二叉树的先序序列是 NLR，后序序列是 LRN。要使 $\mathrm{NLR} = \mathrm{NRL}$（后序序列反序）成立，L 或 R 应为空，这样的二叉树每层只有一个结点，即二叉树的形态是其高度等于结点数。以 3 个结点 $a, b, c$ 为例，其形态如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
### 02. 【解答】
二叉树的先序序列是 NLR，后序序列是 LRN。要使 $\mathrm{NLR} = \mathrm{LRN}$ 成立，L 和 R 均应为空，所以满足条件的二叉树只有一个根结点。
### 03. 【解答】
采用层次遍历的算法，设置变量 level 记录当前结点所在的层数，设置变量 last 指向当前层的最右结点，每次层次遍历出队时与 last 指针比较，若两者相等，则层数加 1，并让 last 指向下一层的最右结点，直到遍历完成。level 的值即二叉树的高度。
算法实现如下：
```c
int Btdepth(BiTree T) {
//采用层次遍历的非递归方法求解二叉树的高度
if (!T)
return 0; //树空，高度为 0
int front=-1, rear=-1; //last 指向当前层的最右结点
int last=0, level=0;
<!-- page: 171 -->
第5章 树与二叉树
159
```cpp
BiTree Q[MaxSize]; //设置队列Q，元素是二叉树结点指针且容量足够
Q[++rear]=T; //将根结点入队
BiTree p;
while(front<rear){ #="" #:="" 0;="" 11="" 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111;="" 0="" 0;="" 1="" 1;="" 1;="" 2="" 2.="" 3="" 4="" 5.="" <table="" [bbox]0.066,0.683,0.286,0.845[="" \="" \mid="" \rarr="" \searrow="" \searrow="" \tag{1111111111111111111111111111111111111111111111111111="" \searrow="" \searrow\="" \searrow\lchild)="" \searrow\lchild)="" \searrow\lchild)="" \searrow\lchild)="" \searrow\lchild)="" \searrow\lchild)="" \searrow\lif(="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" \searrow\lif(0;="" ]="" ```="" ```cpp="" ```cpp="" ```cpp;="" ```cpp;="" ```cpp;="" ```cpp;="" a="" an="" and="" as="" at="" btdepth2(bitree="" btdepth2(t-="" btdepth2(t->lchild);="" btdepth2(t->lchild);="" c="" code="" code;="" code;="" code;="" code;="" code;="" code;="" code;="" code;="" code;="" data="" data,="" de="" depth="" depth1="" depth2="" depth2(a)="" depth;="" depth;="" depth;="" do="" double="" e="" each="" edge="" edge;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" end;="" if="" if(!t)="" if(!t)="" if(!t)="" if(1="" if(1;="" if(1;="" if(1;="" if(1;="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!sempty(q)){="" if(!t)="" if(t="NULL)" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" if(t;="" }="" }="">rdep) return ldep+1; //树的高度为子树最大高度加根结点
else
return rdep+1;
}
```