03. 【解答】
## 03. 【解答】
在完全二叉树中，若第9层是满的，则结点数 $= 2^{9-1} = 256$，而现在第9层只有240个结点，说明第9层未满，是最后一层。 $1 \sim 8$ 层是满的，所以总结点数 $= 2^8 - 1 + 240 = 495$。
因为第9层是最后一层，所以第9层的结点都是叶结点。且第9层的240个结点的双亲在第8层中，其双亲个数为120，即第8层有120个分支结点，其余为叶结点，所以第8层的叶结点数为 $2^{8-1} - 120 = 8$。因此，总的叶结点数 $= 8 + 240 = 248$。
【另解】总结点数 $n = n_0 + n_1 + n_2$，$n_2 = n_0 - 1$，$n = n_0 + n_1 + n_2 = 2n_0 + n_1 - 1$。若 $n_1 = 1$，则 $2n_0 + n_1 - 1 = 2n_0 = 495$，不符合；若 $n_1 = 0$，则 $2n_0 + n_1 - 1 = 2n_0 - 1 = 495$，则 $n_0 = 248$。
## 注意
对于本题，应理解完全二叉树中只有最底层的结点是不满的，其他各层的结点都是满的。
## 04. 【解答】
1）第1层有 $m^0 = 1$ 个结点，第2层有 $m^1$ 个结点，第3层有 $m^2$ 个结点……一般地，第 $i$ 层有 $m^{i-1}$ 个结点（$1 \leqslant i \leqslant h$）。
2）在 $m$ 叉树的情形下，结点 $i$ 的第1个孩子编号为 $j = (i - 1)m + 2$，反过来，结点 $i$ 的双亲的编号是 $\lfloor (i - 2) / m \rfloor + 1$，根结点没有双亲，所以要求 $i > 1$。
3）因为结点 $i$ 的第1个孩子编号为 $(i - 1)m + 2$，若设该结点孩子的序号为 $k = 1,2,\dots ,m$，则第 $k$ 个孩子结点的编号为 $(i - 1)m + k + 1$（$1 \leqslant k \leqslant m$）。
4）结点 $i$ 不是其双亲的第 $m$ 个孩子时才有右兄弟。设其双亲编号为 $j$，可得 $j = \lfloor (i + m - 2) / m \rfloor$，结点 $j$ 的第 $m$ 个孩子的编号为 $(j - 1)m + m + 1 = jm + 1 = \lfloor (i + m - 2) / m \rfloor m + 1$，所以当结点的编号 $i \leqslant \lfloor (i + m - 2) / m \rfloor m$ 时才有右兄弟，右兄弟的编号为 $i + 1$。或者，对于任意一个双亲结点 $j$，其第 $m$ 个孩子结点的编号是 $jm + 1$，故若不为第 $m$ 个孩子结点，则 $(i - 1)\% m! = 0$。
## 05. 【解答】
首先，必须明确二叉树中任意两个结点必然存在最近的公共祖先结点，最坏的情况下是根结点（两个结点分别在根结点的左右分支中），而且从最近的公共祖先结点到根结点的全部祖先结点都是公共的。由二叉树顺序存储的性质可知，任意一个结点 $i$ 的双亲结点的编号为 $i / 2$。求解 $i$ 和 $j$ 最近公共祖先结点的算法步骤如下（设从数组下标1开始存储）：
1）若 $i > j$，则结点 $i$ 所在层次大于或等于结点 $j$ 所在层次。结点 $i$ 的双亲结点为结点 $i / 2$，若 $i / 2 = j$，则结点 $i / 2$ 是原结点 $i$ 和结点 $j$ 的最近公共祖先结点，若 $i / 2 \neq j$，则令 $i = i / 2$，即以该结点 $i$ 的双亲结点为起点，采用递归的方法继续查找。
2）若 $j > i$，则结点 $j$ 所在层次大于或等于结点 $i$ 所在层次。结点 $j$ 的双亲结点为结点 $j / 2$，若 $j / 2 = i$，则结点 $j / 2$ 是原结点 $i$ 和结点 $j$ 的最近公共祖先结点，若 $j / 2 \neq i$，则令 $j = j / 2$。重复上述过程，直到找到它们最近的公共祖先结点为止。
本题代码如下：
ElemType Comm_Ancestor(SqTree T,int i,int j){
//本算法在二叉树中查找结点i和结点j的最近公共祖先结点
if (T[i] != '#' &&T[j] != '#') { //结点存在
while (i != j) { //两个编号不同时循环
if (i > j)
i = i/2; //向上找i的祖先
<!-- page: 152 -->
2027年数据结构考研复习指导
```javascript
else
j = j / 2; //向上找 j 的祖先
}
return T[i];
由解题中算法的步骤描述可知，本题也很容易地联想到采用递归的方法求解。
## 06. 【解答】
1）正则 $k$ 叉树中仅含有两类结点；叶结点（个数记为 $n_0$）和度为 $k$ 的分支结点（个数记为 $n_k$）。树 $T$ 中的结点总数 $n = n_0 + n_k = n_0 + m$。树中所含的边数 $e = n - 1$，这些边均是从 $m$ 个度为 $k$ 的结点发出的，即 $e = mk$。整理得 $n_0 + m = mk + 1$，所以 $n_0 = (k - 1)m + 1$。
2）高度为 $h$ 的正则 $k$ 叉树 $T$ 中，含最多结点的树形为：除第 $h$ 层外，第 1 到第 $h - 1$ 层的结点都是度为 $k$ 的分支结点；而第 $h$ 层均为叶结点，即树是“满”树。此时第 $j$（$1 \leqslant j \leqslant h$）层的结点数为 $k^{j - 1}$，结点总数 $M_{1}$ 为
$$
M _ {1} = \sum_ {j = 1} ^ {h} k ^ {j - 1} = \frac {k ^ {h} - 1}{k - 1}
$$
含最少结点的正则 $k$ 叉树的树形为：第 1 层只有根结点，第 2 到第 $h - 1$ 层仅含 1 个分支结点和 $k - 1$ 个叶结点，第 $h$ 层有 $k$ 个叶结点。也就是说，除根外，第 2 到第 $h$ 层中每层的结点数均为 $k$，所以 $T$ 中所含结点总数 $M_2$ 为
$$
M _ {2} = 1 + (h - 1) k
$$
## 5.3 二叉树的遍历和线索二叉树
### 5.3.1 二叉树的遍历
二叉树的遍历是指按照某种搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次。由于二叉树是一种非线性结构，每个结点最多有两棵子树，因此需要确定一种系统性的访问顺序，将树中结点排列成一个线性序列，以便于后续处理。
**节点追查** ⇒ 二叉树遍历的相关分析（2009、2011、2012）
**节点追查** ⇒ （算法题）二叉树遍历的应用（2014、2017、2022）
根据二叉树的递归定义，遍历一棵二叉树的关键在于确定对根结点（N）、左子树（L）和右子树（R）的访问顺序。在遵循“先左后右”的原则下，常见的遍历方式有三种：先序遍历（NLR）、中序遍历（LNR）和后序遍历（LRN），其中“序”指的是根结点在遍历序列中的位置。
### 1. 先序遍历（PreOrder）
若二叉树为空，则不执行任何操作；否则，
1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。
图 5.7 中的虚线表示对该二叉树进行先序遍历的访问路径，所得先序遍历序列为 124635。
对应的递归算法如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.7 二叉树的先序遍历 <!-- page: 153 --> 第5章 树与二叉树 141 ## 2. 中序遍历（InOrder） 若二叉树为空，则不执行任何操作；否则， 1）中序遍历左子树； 2）访问根结点； 3）中序遍历右子树。 **考虑语法** ➔ 中序序列中结点关系的分析（2017、2024） 图 5.8 中的虚线表示对该二叉树进行中序遍历的访问路径，所得中序遍历序列为 264135。 对应的递归算法如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.8 二叉树的中序遍历 ## 3. 后序遍历（PostOrder） 若二叉树为空，则不执行任何操作；否则， 1）后序遍历左子树； 2）后序遍历右子树； 3）访问根结点。 图 5.9 中的虚线表示对该二叉树进行后序遍历的访问路径，所得后序遍历序列为 642531。 对应的递归算法如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.9 二叉树的后序遍历 上述三种遍历算法中，递归遍历左右子树的顺序都是固定的，区别仅在于访问根结点的时机不同。不论采用哪种遍历方法，每个结点都被访问一次且仅一次，时间复杂度均为 $O(n)$。在递归实现中，系统工作栈的深度等于树的高度，在最坏情况下（如单支树），空间复杂度为 $O(n)$。 ## 4. 层次遍历 图 5.10 展示了二叉树的层次遍历过程，即按照 1, 2, 3, 4 的层次顺序，以及箭头所指方向，从上到下、从左到右逐层访问二叉树中的各结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.10 二叉树的层次遍历 <!-- page: 154 --> 2027年数据结构考研复习指导 层次遍历需要借助一个队列，其基本思想如下：首先将根结点入队，随后不断出队并访问队头结点，同时将其存在的左右孩子依次加入队尾，直至队列为空。 二叉树的层次遍历算法如下：读者可将上述层次遍历算法作为一个模板，熟练掌握其执行过程，并达到熟练手写的程度。 ## 注意 遍历是二叉树各类操作的基础。例如，对于一棵给定二叉树，求结点的双亲、查找孩子结点、计算树的深度、统计叶结点数、判断两棵二叉树是否相同等操作，本质上都是在某种遍历过程中完成的。因此，必须深入理解并灵活运用各种遍历方法，以解决实际问题。 ## 5. 由遍历序列构造二叉树 **考虑点击** 先序序列对应的不同二叉树的分析（2015） 对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是唯一确定的。然而，仅凭这四种遍历序列中的任意一种，却无法唯一确定这棵二叉树。但若已知中序序列，并辅以其他三种遍历序列中的任意一种，则可以唯一地重构出该二叉树。 （1）由先序序列和中序序列构造二叉树 **考虑点击** 先序序列和中序序列相同时确定的二叉树（2017） **考虑点击** 由先序序列和中序序列构造一棵二叉树（2020、2021） 在先序序列中，第一个结点必定是整棵二叉树的根结点；而在中序遍历中，根结点将中序序列划分为两个子序列：左侧子序列为左子树的中序序列，右侧子序列为右子树的中序序列。由于左右子树的结点数在先序和中序序列中一致，因此可据此从先序序列中分离出左右子树各自的先序子序列，如图5.11所示。通过递归地对左右子树重复上述过程，即可唯一地确定整棵二叉树。void LevelOrder(BiTree T) { InitQueue(Q); //初始化辅助队列 BiTree p; EnQueue(Q, T); //将根结点入队 while(!IsEmpty(Q)) { //队列不空则循环 DeQueue(Q, p); //队头结点出队 visit(p); //访问出队结点 if(p-&gt;lchild!=NULL) EnQueue(Q, p-&gt;lchild); //若左孩子不空，则左孩子入队 if(p-&gt;rchild!=NULL) EnQueue(Q, p-&gt;rchild); //若右孩子不空，则右孩子入队 } }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.11 由先序序列和中序序列构造二叉树 例如，求先序序列（ABCDEFGHI）和中序序列（BCAEDGHFI）所确定的二叉树。首先，由先序序列可知 $A$ 为根结点。在中序序列中，$A$ 左侧的 $BC$ 构成左子树的中序序列，右侧的 EDGHFI <!-- page: 155 --> 第5章 树与二叉树 143 构成右子树的中序序列。然后，由先序序列可知 $B$ 是左子树的根结点，$D$ 是右子树的根结点。以此类推，将剩余结点递归分解，最终构造出的二叉树如图 5.12(c) 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 图 5.12 一棵二叉树的构造过程 （2）由后序序列和中序序列构造二叉树 **特点说明** ▶ 由后序序列和树形构造一棵二叉树（2017、2023） 同理，后序序列与中序序列也可唯一确定一棵二叉树。后序序列的最后一个结点即为整棵树的根结点，它同样能将中序序列划分为左右子树的中序序列。随后，根据左右子树的结点数，可从后序序列中分离出对应的左右子树的后序序列，并递归构造，如图 5.13 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.13 由后序序列和中序序列构造二叉树 请读者分析后序序列（CBEHGIFDA）和中序序列（BCAEDGHF I）所确定的二叉树。 （3）由层序序列和中序序列构造二叉树 在层序序列中，第一个结点必为二叉树的根结点，由此可在中序序列中划分出左右子树的中序序列。若存在左子树，则层序序列的第二个结点一定是左子树的根，可以进一步划分左子树；若存在右子树，则层序序列中紧接着的下一个结点一定是右子树的根，可以进一步划分右子树，如图 5.14 所示。通过逐层确定各子树的根结点并递归划分，即可唯一确定这棵二叉树。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.14 由层序序列和中序序列构造二叉树 请读者分析层序序列（ABDCEFGIH）和中序序列（BCAEDGHFI）所确定的二叉树。 注意，仅凭先序、后序和层序序列中的任意两种组合，通常无法唯一确定一棵二叉树。例如，图 5.15 所示的两棵二叉树的先序序列均为 $AB$，后序序列均为 $BA$，层序序列均为 $AB$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.15 两棵不同的二叉树
## 5.3.2 线索二叉树
### 1. 线索二叉树的基本概念
遍历二叉树是按照特定规则将树中所有结点排列成一个线性序列，从而得到相应的遍历序
<!-- page: 156 -->
2027年数据结构考研复习指导
列。在该序列中，除首尾结点外，每个结点都有唯一的直接前驱和直接后继。
**考点建议** 线索二叉树的定义（2010）
传统的二叉链表结构仅能反映父子关系，无法直接获取结点在某种遍历序列中的前驱或后继。前面提到，在含有 $n$ 个结点的二叉树中，共有 $n + 1$ 个空指针域；每个叶结点贡献2个空指针，每个度为1的结点贡献1个空指针，因此空指针总数为 $2n_{0} + n_{1}$ ，又 $n_{0} = n_{2} + 1$ ，可得空指针总数为 $n_{0} + n_{1} + n_{2} + 1 = n + 1$ 。由此，自然想到：可否利用这些空指针，直接指向结点在遍历序列中的前驱或后继？若能实现，便可像遍历链表一样高效地遍历二叉树，线索二叉树正是基于这一思想设计的。
具体规定如下：
- 若某结点无左子树，则将 lchild 指向其在指定遍历序列中的前驱结点。
- 若某结点无右子树，则将 rchild 指向其在指定遍历序列中的后继结点。
为区分指针域指向的是孩子还是线索，需在结点结构中增设两个标志域，如图5.16所示。
| lchild | ltag | data | rtag | rchild |
| --- | --- | --- | --- | --- |
图5.16 线索二叉树的结点结构
标志域ltag和rtag的含义如下：
- ltag=0表示lchild指向左孩子，ltag=1表示lchild指向前驱。
- $\mathbf{r}\mathbf{t}\mathbf{a}\mathbf{g} = 0$ 表示 rchild 指向右孩子， $\mathbf{r}\mathbf{t}\mathbf{a}\mathbf{g} = 1$ 表示 rchild 指向后继。
线索二叉树的存储结构可定义为：
采用上述结构的二叉链表称为线索链表，其中指向前驱或后继的指针称为线索。这种带有线索的二叉树称为线索二叉树。
## 2. 中序线索二叉树的构造
二叉树的线索化是指将二叉链表中的空指针域替换为指向前驱或后继的线索。由于结点的前驱和后继关系只能在遍历过程中确定，因此线索化本质上就是对二叉树进行一次遍历。
**考点建议** 中序线索二叉树中线索的指向（2014）
以中序线索二叉树的构造为例：设指针pre指向刚刚访问过的结点，指针p指向当前正在访问的结点，pre即为p的中序前驱。在中序遍历过程中：检查p的左指针是否为空，若为空则令其指向pre：检查pre的右指针是否为空，若为空则令其指向p，如图5.17所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.17 中序线索二叉树及其二叉链表示 通过中序遍历对二叉树线索化的递归算法如下：建立中序线索二叉树的主过程如下： 为方便遍历，可在线索链表上增设一个头结点：其 lchild 指向根结点；rchild 指向中序序列的最后一个结点；中序序列的第一个结点的 lchild 和最后一个结点的 rchild 均指向头结点。如此，便形成一个双向循环线索链表，从而支持正向与反向的高效遍历，如图 5.18 所示。void InThread(ThreadTree &amp;p, ThreadTree &amp;pre) { if (p != NULL) { <!-- page: 157 --> 第5章 树与二叉树 145 ```c InThread(p-&gt;lchild,pre); //递归，线索化左子树 if (p-&gt;lchild==NULL) { //当前结点的左子树为空 p-&gt;lchild=pre; //建立当前结点的前驱线索 p-&gt;ltag=1; } if (pre!=NULL&amp;&amp;pre-&gt;rchild==NULL) { //前驱结点非空且其右子树为空 pre-&gt;rchild=p; //建立前驱结点的后继线索 pre-&gt;rtag=1; } pre=p; //标记当前结点成为刚刚访问过的结点 InThread(p-&gt;rchild,pre); //递归，线索化右子树 }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.18 带头结点的中序线索二叉树 ## 3. 中序线索二叉树的遍历 中序线索二叉树的结点中已隐含前驱和后继信息，因此遍历时无须借助栈或递归。只需先找到中序序列的第一个结点，然后依次查找每个结点的后继，直至后继为空（或回到头结点）。在中序线索二叉树中，查找结点后继的规则如下：若结点的 rtag 为 1，则 rchild 直接指向其后继；若 rtag 为 0，则其后继为右子树中最左下结点（右子树的中序第一个结点）。 不含头结点的中序线索二叉树遍历相关算法如下。 1）求中序序列中的第一个结点： 2）求结点 p 在中序序列中的后继： ```c ThreadNode *Nextnode(ThreadNode *p) { if (p->rtag==0) return Firstnode(p->rchild); //右子树中最左下结点 else return p->rchild; //若 rtag==1 则直接返回后继线索 } } <!-- page: 158 --> 2027年数据结构考研复习指导 请读者自行完成求中序序列中的最后一个结点和结点 p 的中序前驱的运算①。 3）利用上面两个算法，可实现非递归的中序遍历： ```c void Inorder(ThreadNode *T) { for (ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p)) visit(p); } ```