4. 先序线索二叉树和后序线索二叉树
## 4. 先序线索二叉树和后序线索二叉树 建立先序或后序线索二叉树的方法与中序类似，只需调整递归调用顺序及线索建立的位置。以图 5.19(a) 的二叉树为例，手工构造先序线索二叉树的过程如下（先序序列为 $ABCDF$，依次处理每个结点，若其左或右指针为空，则将其替换为对应前驱或后继的线索）： 结点 $A$、$B$ 均有左右孩子，无须修改指针；结点 $C$ 无左孩子，将其 lchild 指向前驱 $B$，无右孩子，将其 rchild 指向后继 $D$；结点 $D$ 无左孩子，将其 lchild 指向前驱 $C$，无右孩子，将其 rchild 指向后继 $F$；结点 $F$ 无左孩子，将其 lchild 指向前驱 $D$，无右孩子且无后继，将其 rchild 置为空，最终得到的先序线索二叉树如图 5.19(b) 所示。 构造后序线索二叉树的过程类似（后序序列为 CDBFA）： 结点 $C$ 无左孩子且无前驱，将 lchild 置空，无右孩子，将 rchild 指向后继 $D$；结点 $D$ 无左孩子，将 lchild 指向前驱 $C$，无右孩子，将 rchild 指向后继 $B$；结点 $F$ 无左孩子，将 lchild 指向前驱 $B$，无右孩子，将 rchild 指向后继 $A$，得到的后序线索二叉树如图 5.19(c) 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 一颗二叉树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 先序线索二叉树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 后序线索二叉树
图 5.19 先序线索二叉树和后序线索二叉树
在先序线索二叉树中查找某结点的后继较为直接：若该结点有左孩子，则左孩子为其后继；若无左孩子但有右孩子，则右孩子为其后继；若为叶结点，则其 rchild 直接指向后继。
**修改通知** 后序线索二叉树的特点（2013）
而在后序线索二叉树中查找后继则较为复杂，需要分以下三种情况：① 若结点 $x$ 是整棵二叉树的根，则其后继为空；② 若结点 $x$ 是其双亲的右孩子，或是其双亲的左孩子且该双亲无右子树，则 $x$ 的后继即为其双亲；③ 若结点 $x$ 是其双亲的左孩子，且该双亲存在右子树，则 $x$ 的后继为该右子树中按后序遍历访问的第一个结点（右子树中最左下结点）。
值得注意的是，图 5.19(c) 中，结点 $B$ 的后继是 $A$，但无法直接通过线索找到后继，需要回溯到其双亲。因此，在后序线索二叉树中高效查找后继通常需要知道结点的父结点信息。为此，通常采用带父指针的三叉链表作为存储结构，而非标准的二叉线索链表。
## 5.3.3 本节试题精选
### 一、单项选择题
01. 在下列关于二叉树遍历的说法中，正确的是（）。
① 将函数 1 中的 ltag 和 lchild 替换为 rtag 和 rchild，并向右下方查找，即为求中序序列的最后一个结点。将函数 2 中的 rtag 和 rchild 替换为 ltag 和 lchild，调用函数替换为求左子树的中序序列的最后一个结点，即为求中序序列中结点 p 的前驱。
<!-- page: 159 -->
第5章 树与二叉树
147
A. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点
B. 若有一个结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
C. 若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结点
D. 若有一个叶结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
02. 在任何一棵二叉树中，若结点 $a$ 有左孩子 $b$、右孩子 $c$，则在结点的先序序列、中序序列、后序序列中，（）。
A. 结点 $b$ 一定在结点 $a$ 的前面
B. 结点 $a$ 一定在结点 $c$ 的前面
C. 结点 $b$ 一定在结点 $c$ 的前面
D. 结点 $a$ 一定在结点 $b$ 的前面
03. 设 $n, m$ 为一棵二叉树上的两个结点，在中序遍历时，$n$ 在 $m$ 前的条件是（）。
A. $n$ 在 $m$ 右方
B. $n$ 是 $m$ 祖先
C. $n$ 在 $m$ 左方
D. $n$ 是 $m$ 子孙
04. 设 $n, m$ 为一棵二叉树上的两个结点，在后序遍历时，$n$ 在 $m$ 前的充分条件是（）。
A. $n$ 在 $m$ 右方
B. $n$ 是 $m$ 祖先
C. $n$ 在 $m$ 左方
D. $n$ 是 $m$ 子孙
05. 某非空二叉树采用顺序存储结构，树中的结点信息按完全二叉树的层次序列依次存放在如下所示的一维数组中，则该二叉树的后序遍历序列为（）。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| a | b | c | | d | e | f | | | g | | | h |
A. ghbefhca
B. gbdehcfa
C. gdbhefca
D. bgdehcfa
06. 在二叉树的先序序列、中序序列和后序序列中，所有叶结点的先后顺序（）。
A. 都不相同
B. 完全相同
C. 先序和中序相同，而与后序不同
D. 中序和后序相同，而与先序不同
07. 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）次序的遍历实现编号。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
08. 按某种顺序对二叉树的结点进行编号，编号为 $1,2,\dots ,n$，规定：树中任一结点 $v$，其编号等于 $v$ 的左子树上的最小编号减 1，而 $v$ 的右子树中的最小编号等于 $v$ 的左子树上的最大编号加 1，则说明该二叉树是按（ ）次序编号的。
A. 中序遍历
B. 先序遍历
C. 后序遍历
D. 层次遍历
09. 先序序列为 $A, B, C$，后序序列为 $C, B, A$ 的二叉树共有（）。
A. 1 棵
B. 2 棵
C. 3 棵
D. 4 棵
10. 一棵完全二叉树的后序遍历序列为 CDBFGEA，则其先序遍历序列是（）。
A. CBDAFEG
B. ABECDFG
C. ABCDEFG
D. 无法确定
11. 设结点 $X$ 和 $Y$ 是二叉树中任意的两个结点。在该二叉树的先序遍历序列中 $X$ 在 $Y$ 之前，而在其后序遍历序列中 $X$ 在 $Y$ 之后，则 $X$ 和 $Y$ 的关系是（）。
A. $X$ 是 $Y$ 的左兄弟
B. $X$ 是 $Y$ 的右兄弟
C. $X$ 是 $Y$ 的祖先
D. $X$ 是 $Y$ 的后裔
<!-- page: 160 -->
2027年数据结构考研复习指导
12. 若二叉树中结点的先序序列是 $\dots a \dots b \dots$，中序序列是 $\dots b \dots a \dots$，则（）。
A. 结点 $a$ 和结点 $b$ 分别在某结点的左子树和右子树中
B. 结点 $b$ 在结点 $a$ 的右子树中
C. 结点 $b$ 在结点 $a$ 的左子树中
D. 结点 $a$ 和结点 $b$ 分别在某结点的两棵非空子树中
13. 一棵二叉树的先序遍历序列为1234567，它的中序遍历序列可能是（）。
A. 3124567
B. 1234567
C. 4135627
D. 1463572
14. 下列序列中，不能唯一地确定一棵二叉树的是（）。
A. 层次序列和中序序列
B. 先序序列和中序序列
C. 后序序列和中序序列
D. 先序序列和后序序列
15. 若一棵二叉树的中序序列和后序序列相同，则（）。
A. 二叉树为空树或二叉树任一结点没有左子树
B. 二叉树为空树或二叉树任一结点没有右子树
C. 二叉树为空树或二叉树中每个结点的度为1
D. 二叉树为空树或二叉树为满二叉树
16. 已知一棵二叉树的后序序列为 DABEC，中序序列为 DEBAC，则先序序列为（）。
A. ACBED
B. DECAB
C. DEABC
D. CEDBA
17. 已知一棵二叉树的先序遍历结果为 $ABCDEF$，中序遍历结果为 $CBAEDF$，则后序遍历的结果为（）。
A. CBEFDA
B. FEDCBA
C. CBEDFA
D. 不确定
18. 已知一棵二叉树的层次序列为 $ABCDEF$，中序序列为 $BADCFE$，则先序序列为（）。
A. ACBEDF
B. $ABCDEF$
C. $BDFECA$
D. $FCEDBA$
19. 某二叉树中结点 $x$ 在先序、中序、后序遍历序列中的编号分别为 $\operatorname{pre}(x)、\operatorname{in}(x)、\operatorname{post}(x)$（假设都从1开始依次顺序编号），$a$ 和 $b$ 是该二叉树中的两个结点，其中 $a$ 是 $b$ 的祖先，则下列选项中不可能出现的是（）。
A. $\operatorname{pre}(a) < \operatorname{pre}(b)$
B. $\operatorname{post}(a) < \operatorname{post}(b)$
C. $\operatorname{in}(a) < \operatorname{in}(b)$
D. $\operatorname{in}(a) > \operatorname{in}(b)$
20. 某二叉树采用二叉链表存储结构，若要删除该二叉链表中的所有结点，并释放它们占用的存储空间，则采用（）遍历方法最合适。
A. 中序
B. 层次
C. 后序
D. 先序
21. 某二叉树 $T$ 采用二叉链表存储结构，$T$ 的中序遍历序列为一个升序序列，要求采用某种方法对 $T$ 进行某种操作之后得到一棵新的二叉树 $T'$，要求 $T'$ 的中序遍历序列为一个降序序列，则下列关于该算法的叙述中，正确的是（）。
A. 采用中序遍历的方法最合适
B. 采用后序遍历的方法最合适
C. $T'$ 中的根结点一定不是原 $T$ 中的根结点
D. $T'$ 中的叶结点不一定是原 $T$ 中的叶结点
22. 引入线索二叉树的目的是（）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便插入和删除
C. 为了能方便找到双亲
D. 使二叉树的遍历结果唯一
23. $n$ 个结点的线索二叉树上含有的线索数为（）。
A. $2n$
B. $n - 1$
C. $n + 1$
D. $n$
24. 判断线索二叉树中 $*p$ 结点有右孩子结点的条件是（）。
A. $p! = NULL$
B. $p -> rchild! = NULL$
<!-- page: 161 -->
第5章 树与二叉树
149
C. p->rtag==0
D. p->rtag==1
25. 一裸左子树为空的二叉树在先序线索化后，其中空的链域的个数是（ ）。
A. 不确定
B. 0 个
C. 1 个
D. 2 个
26. 在线索二叉树中，下列说法不正确的是（ ）。
A. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的最左下结点
B. 在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的最右下结点
C. 线索二叉树是利用二叉树的 $n + 1$ 个空指针来存放结点的前驱和后继信息的
D. 每个结点通过线索都可以直接找到它的前驱和后继
27. 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 先序线索二叉树中求先序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
28. 若 $X$ 是二叉中序线索树中一个有左孩子的结点，且 $X$ 不为根，则 $X$ 的前驱为（ ）。
A. $X$ 的双亲
B. $X$ 的右子树中最左的结点
C. $X$ 的左子树中最右的结点
D. $X$ 的左子树中最右的叶结点
29. 若 $X$ 是后序线索二叉树中的叶结点，且 $X$ 存在左兄弟 $Y$，则 $X$ 的右线索指向的是（ ）。
A. $X$ 的双亲
B. 以 $Y$ 为根的子树的最左下结点
C. $X$ 的左兄弟 $Y$
D. 以 $Y$ 为根的子树的最右下结点
30. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任意一个结点无左孩子
D. 任意一个结点无右孩子
31. 某非空二叉树的先序序列和中序序列正好相反，则下列叙述中正确的是（ ）。
A. 该二叉树一定只有一个结点
B. 只有一个叶结点的二叉树一定满足条件
C. 任意一个结点无左孩子的二叉树一定满足条件
D. 任意一个结点无右孩子的二叉树一定满足条件
32.【2009统考真题】给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3175624，则其遍历方式是（ ）。
A. LRN
B. NRL
C. RLN
D. RNL
33.【2010统考真题】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D. 34.【2011统考真题】一裸二叉树的先序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，该二叉树的中序遍历序列不会是（ ）。 A. 1,2,3,4 B. 2,3,4,1 C. 3,2,4,1 D. 4,3,2,1 <!-- page: 162 --> 2027年数据结构考研复习指导 35. 【2012 统考真题】若一裸二叉树的先序遍历序列为 $a, e, b, d, c$，后序遍历序列为 $b, c, d, e, a$，则根结点的孩子结点（）。 A. 只有 $e$ B. 有 $e, b$ C. 有 $e, c$ D. 无法确定 36. 【2013 统考真题】若 $X$ 是后序线索二叉树中的叶结点，且 $X$ 存在左兄弟结点 $Y$，则 $X$ 的右线索指向的是（）。 A. $X$ 的父结点 B. 以 $Y$ 为根的子树的最左下结点 C. $X$ 的左兄弟结点 $Y$ D. 以 $Y$ 为根的子树的最右下结点 37. 【2014 统考真题】若对右图所示的二叉树进行中序线索化，则结点 $X$ 的左右线索指向的结点分别是（）。 A. $e, c$ B. $e, a$ C. $d, c$ D. $b, a$ 38. 【2015 统考真题】先序序列为 $a, b, c, d$ 的不同二叉树的个数是（）。 A. 13 B. 14 C. 15 D. 16 39. 【2017 统考真题】某二叉树的树形如右图所示，其后序序列为 $e, a, c, b, d, g, f$，树中与结点 $a$ 同层的结点是（）。 A. $c$ B. $d$ C. $f$ D. $g$ 40. 【2017 统考真题】要使一裸非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（）。 A. 只有左子树 B. 只有右子树 C. 结点的度均为 1 D. 结点的度均为 2 41. 【2022 统考真题】若结点 $p$ 与 $q$ 在二叉树 $T$ 的中序遍历序列中相邻，且 $p$ 在 $q$ 之前，则下列 $p$ 与 $q$ 的关系中，不可能的是（）。 I. $q$ 是 $p$ 的双亲 II. $q$ 是 $p$ 的右孩子 III. $q$ 是 $p$ 的右兄弟 IV. $q$ 是 $p$ 的双亲的双亲 A. 仅 I B. 仅 III C. 仅 II, III D. 仅 II, IV 42. 【2023 统考真题】已知一裸二叉树的树形如右图所示，若其后序遍历序列为 $fdbeca$，则其先（前）序遍历序列是（）。 A. $aedfbc$ B. $acebdf$ C. $cabefd$ D. $dfebac$ 43. 【2024 统考真题】若 $p, q$ 和 $v$ 均为二叉树 $T$ 中的结点，$v$ 有两个孩子结点，$T$ 的中序遍历序列形如“…,$p, v, q, …”，则在下列叙述中，正确的是（）。 A. $p$ 没有右孩子，$q$ 没有左孩子 B. $p$ 没有右孩子，$q$ 有左孩子 C. $p$ 有右孩子，$q$ 没有左孩子 D. $p$ 有右孩子，$q$ 有左孩子
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
# 二、综合应用题
01. 若某非空二叉树的先序序列和后序序列正好相反，则该二叉树的形态是什么？
02. 若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？
03. 假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
04. 二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否是完全二叉树的算法。
05. 假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一裸给定二叉树的所有双分支结点数。
06. 设树 $B$ 是一裸采用链式结构存储的二叉树，编写一个把树 $B$ 中所有结点的左右子树进行交换的函数。
<!-- page: 163 -->
第5章 树与二叉树
151
07. 假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第 $k$（$1 \leqslant k \leqslant$ 二叉树中结点数）个结点的值。
08. 已知二叉树以二叉链表存储，编写算法完成；对于树中每个元素值为 $x$ 的结点，删除以它为根的子树，并释放相应的空间。
09. 在二叉树中查找值为 $x$ 的结点，试编写算法（用 C 语言）打印值为 $x$ 的结点的所有祖先，假设值为 $x$ 的结点不多于一个。
10. 设一棵二叉树的结点结构为 (LLINK, INFO, RLINK)，ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写算法 ANCESTOR (ROOT, p, q, r)，找到p和q的最近公共祖先结点r。
11. 假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树 $b$ 的宽度（具有结点数最多的那一层的结点数）。
12. 设有一棵满二叉树（所有结点值均不同），已知其先序序列为 $pre$，设计一个算法求其后序序列 $post$。
13. 设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为 head。二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针。
14. 试设计判断两棵二叉树是否相似的算法。所谓二叉树 $T_{1}$ 和 $T_{2}$ 相似，指的是 $T_{1}$ 和 $T_{2}$ 都是空的二叉树或都只有一个根结点；或者 $T_{1}$ 的左子树和 $T_{2}$ 的左子树是相似的，且 $T_{1}$ 的右子树和 $T_{2}$ 的右子树是相似的。
15. 【2014 统考真题】二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 $T$，采用二叉链表存储，结点结构为
| left | weight | right |
| --- | --- | --- |
其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 $T$ 的根结点的指针，请设计求 $T$ 的 WPL 的算法，要求：
1）给出算法的基本设计思想。
2）使用C或C++语言，给出二叉树结点的数据类型定义。
3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
16. 【2017 统考真题】请设计一个算法，将给定的表达式树（二叉树）转换为等价的中级表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
输出的等价中级表达式分别为 $(a + b) * (c * (-d))$ 和 $(a * b) + (-(c - d))$。 二叉树结点定义如下： 要求： 1）给出算法的基本设计思想。 <!-- page: 164 --> 2027年数据结构考研复习指导 2）根据设计思想，采用C或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。 17. 【2022 统考真题】已知非空二叉树 $T$ 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下： $T$ 中不存在的结点在数组 SqBiTNode 中用 -1 表示。例如，对于下图所示的两棵非空二叉树 $T_1$ 和 $T_2$，
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
二叉树 $T_1$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
二叉树 $T_2$
$T_{1}$ 的存储结果如下：
T1.SqBiTNode
| 40 | 25 | 60 | -1 | 30 | -1 | 80 | -1 | -1 | 27 | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
T1.ElemNum=10
$T_{2}$ 的存储结果如下：
T2.SqBiTNode
| 40 | 50 | 60 | -1 | 30 | -1 | -1 | -1 | -1 | -1 | 35 | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
T2.ElemNum=11
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉拔索树，若是，则返回 true，否则，返回 false。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。