归纳总结
# 归纳总结 学习 KMP 算法时，应从暴力匹配的低效性入手：主串指针的回溯会导致大量重复比较。实际上，已匹配的部分恰好是模式串的一个前缀，而每次回溯相当于将模式串与其自身的某个前缀反复比对。为了提升效率，需要深入分析模式串自身的结构。当某个字符失配时，若已匹配部分存在一个与模式串前缀相等的后缀（最长相等前后缀），则可将模式串滑动至该前后缀对齐的位置（对齐部分显然无须重新比较），直接从主串当前失配位置继续匹配即可。KMP 算法的核心是通过预计算每个失配位置的最佳跳转位置（如 next 数组），避免无效比较，从而实现高效匹配。 # 思维拓展 编程实现：模式串在主串中有多少个完全匹配的子串？注意，线考应不会考 KMP 算法题。 # 购买王道书，就上 # 王道官方考研书店 wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 136 --> 第5章 # 树与二叉树 ## 【考纲内容】 （一）树的基本概念 （二）二叉树 二叉树的定义及其主要特征；二叉树的顺序存储结构和链式存储结构； 二叉树的遍历；线索二叉树的基本概念和构造 （三）树、森林 树的存储结构；森林与二叉树的转换；树和森林的遍历 （四）树与二叉树的应用 哈夫曼（Huffman）树和哈夫曼编码；并查集及其应用；堆及其应用 ## 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 【复习提示】
本章内容主要以选择题和综合题形式考查，统考中也可能出现与树遍历相关的算法题。树与二叉树的基本性质、遍历操作、相互转换、存储结构及操作特性，以及满二叉树、完全二叉树、线索二叉树和哈夫曼树的定义与性质，均为选择题的高频考点。
# 5.1 树的基本概念
## 5.1.1 树的定义
树是 $n$（$n \geqslant 0$）个结点的有限集。当 $n = 0$ 时，称为空树。在任意一棵非空树中必须满足：
1）有且仅有一个特定的结点称为棋结点。
<!-- page: 137 -->
第5章 树与二叉树
125
2）当 $n > 1$ 时，其余结点可分为 $m（m > 0$ ）个互不相交的有限集 $T_{1}, T_{2}, \dots, T_{m}$ ，其中每个集合本身又是一棵树，称为根的子树。
显然，树的定义是递归的——在定义中引用了自身，因此树是一种典型的递归数据结构。作为一种逻辑结构，树同时也是一种分层结构，具有以下两个特征：
1）根结点没有前驱，除根结点外的每个结点有且仅有一个前驱。
2）所有结点均可拥有零个或多个后继。
树适用于表示具有层次结构的数据。除根结点外，树中任一结点最多只与上一层的一个结点（其父结点）存在直接关联；根结点则无上层结点。因此，在包含 $n$ 个结点的树中，恰好存在 $n - 1$ 条边。同时，每个结点可与其下一层的零个或多个结点（其孩子结点）建立直接联系。
## 5.1.2 基本术语
下面结合图5.1中的树来说明一些基本术语和概念。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.1 树的树形表示
1）祖先、子孙、双亲、孩子、兄弟和堂兄弟。
考虑结点 $K$ ，从根 $A$ 到结点 $K$ 的唯一路径上所经过的所有其他结点，称为 $K$ 的祖先。例如，结点 $B$ 是 $K$ 的祖先，而 $K$ 是 $B$ 的子孙； $B$ 的子孙包括 $E, F, K, L$ 。该路径上最接近 $K$ 的结点 $E$ 称为 $K$ 的双亲， $K$ 则是 $E$ 的孩子。根结点 $A$ 是树中唯一没有双亲的结点。具有相同双亲的结点互为兄弟，如 $K$ 与 $L$ 的双亲均为 $E$ ，故 $K$ 与 $L$ 为兄弟。若两个结点的双亲位于同一层，则它们互为堂兄弟，如 $G$ 与 $E, F, H, I, J$ 互为堂兄弟。
2）结点的层次、深度和高度。
结点的层次从根开始定义：根为第1层，其孩子为第2层，以此类推。结点的深度即为其所在的层次。树的高度（或深度）是树中结点的最大层数。而结点的高度是指以其为根的子树的高度。图5.1中树的高度为4。
3）结点的度和树的度。
树中一个结点的孩子个数称为该结点的度；树中所有结点的度的最大值称为树的度。例如，结点 $B$ 的度为2，结点 $D$ 的度为3，因此该树的度为3。
4）分支结点和叶结点。
度大于0的结点称为分支结点（也称非终端结点）；度为0（无孩子）的结点称为叶结点（也称终端结点）。在分支结点中，每个结点的分支数即为其度。
5）有序树和无序树。
若树中各结点的子树从左到右具有固定次序、不可互换，则称为有序树；否则称为无序树。假设图5.1为有序树，若交换某结点的子结点位置，则得到一棵不同的树。
6）路径和路径长度。
树中两个结点之间的路径是由从一个结点到另一个结点所经过的结点序列构成的，路径长度则是该路径上边的数目。
<!-- page: 138 -->
2027年数据结构考研复习指导
7）森林。
考点信息
森林中树的数量、边数和结点数的关系（2016）
森林是 $m$（$m \geqslant 0$）棵互不相交的树的集合。森林与树的概念密切相关：将树的根结点移除后，其各子树构成一个森林；反之，若为 $m$ 棵独立的树添加一个新结点，并将其作为这 $m$ 棵树的共同根，则森林便转化为一棵树。
注意
上述概念无须元记硬背，结合实例理解即可。考研通常不会直接考查定义，而是融入具体题目中综合考查。做题时若遇到不熟悉的概念，可随时查阅；随着练习增多，自然能够熟练掌握。
5.1.3 树的性质
树具有如下基本性质：
考点信息
树中结点数和度数的关系分析（2010、2016）
1）树的结点数 $n$ 等于所有结点的度数之和加 1。
结点与其每个孩子都有唯一的边相连，因此树中所有结点的度数之和等于边数；又因除根结点外每个结点均有唯一双亲，故结点数 $n$ 等于边数加1，即所有结点的度数之和加1。
2）度为 $m$ 的树中，第 $i$ 层上至多有 $m^{i-1}$ 个结点（$i \geqslant 1$）。
第1层至多有1个结点（根结点）；第2层至多有 $m$ 个结点；第3层至多有 $m^2$ 个结点，以此类推。通过数学归纳法可以证明，第 $i$ 层至多有 $m^{i-1}$ 个结点。
3）高度为 $h$ 的 $m$ 义树至多有 $(m^h - 1) / (m - 1)$ 个结点。
当各层结点数达到最大时，树中至多有 $1 + m + m^2 + \dots + m^{h - 1} = (m^h - 1) / (m - 1)$ 个结点。
考点信息
指定结点数的三叉树的最小高度分析（2022）
4）度为 $m$、具有 $n$ 个结点的树的最小高度 $h$ 为 $\lceil \log_m(n(m - 1) + 1) \rceil$。
要使高度最小，树应尽可能饱满，即前 $h - 1$ 层每层的结点数均达到最大值。前 $h - 1$ 层最多有 $(m^{h - 1} - 1) / (m - 1)$ 个结点，前 $h$ 层最多有 $(m^h - 1) / (m - 1)$ 个结点。因此，$(m^{h - 1} - 1) / (m - 1) < n \leqslant (m^h - 1) / (m - 1)$，即 $h - 1 < \log_m(n(m - 1) + 1) \leqslant h$，解得 $h_{\min} = \lceil \log_m(n(m - 1) + 1) \rceil$。
5）度为 $m$、具有 $n$ 个结点的树的最大高度 $h$ 为 $n - m + 1$。
树的度为 $m$，因此至少有一个结点有 $m$ 个孩子，它们处于同一层。为使树的高度最大，其他层可仅有一个结点，因此最大高度（层数）为 $n - m + 1$。由此，也可逆推出高度为 $h$、度为 $m$ 的树至少包含 $h + m - 1$ 个结点。
5.1.4 本节试题精选
一、单项选择题
01. 树最适合用来表示（ ）的数据。
A. 有序
B. 无序
C. 任意元素之间具有多种联系
D. 元素之间具有分支层次关系
02. 一棵有 $n$ 个结点的树的所有结点的度数之和为（ ）。
A. $n - 1$
B. $n$
C. $n + 1$
D. $2n$
03. 树的路径长度是从树根到每个结点的路径长度的（ ）。
A. 总和
B. 最小值
C. 最大值
D. 半均值
<!-- page: 139 -->
第5章 树与二义树
127
04. 对于一裸具有 $n$ 个结点、度为 4 的树来说，（ ）。
A. 树的高度至多是 $n - 3$
B. 树的高度至多是 $n - 4$
C. 第 $i$ 层上至多有 $4(i - 1)$ 个结点
D. 至少在某一层上正好有 4 个结点
05. 度为 4、高度为 $h$ 的树，（ ）。
A. 至少有 $h + 3$ 个结点
B. 至多有 $4h - 1$ 个结点
C. 至多有 $4h$ 个结点
D. 至少有 $h + 4$ 个结点
06. 假定一裸度为 3 的树中，结点数为 50，则其最小高度为（ ）。
A. 3
B. 4
C. 5
D. 6
07. 设有一裸度为 3 的树，其中度为 3 的结点数 $n_3 = 2$，度为 2 的结点数 $n_2 = 1$，叶结点数 $n_0 = 6$，则该树的结点总数为（ ）。
A. 12
B. 9
C. 10
D. $\geqslant 9$ 的任意整数
08. 设一裸 $m$ 义树中有 $N_{1}$ 个度数为 1 的结点，$N_{2}$ 个度数为 2 的结点……$N_{m}$ 个度数为 $m$ 的结点，则该树中共有（ ）个叶结点。
A. $\sum_{i = 1}^{m}(i - 1)N_{i}$
B. $\sum_{i = 1}^{m}N_{i}$
C. $\sum_{i = 2}^{m}(i - 1)N_{i}$
D. $\sum_{i = 2}^{m}(i - 1)N_{i} + 1$
09. 【2010 统考真题】在一裸度为 4 的树 $T$ 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 $T$ 的叶结点数是（ ）。
A. 41
B. 82
C. 113
D. 122
10. 【2016 统考真题】若森林 $F$ 有 15 条边、25 个结点，则 $F$ 包含树的个数是（ ）。
A. 8
B. 9
C. 10
D. 11
## 二、综合应用题
01. 含有 $n$ 个结点的三义树的最小高度是多少？
02. 已知一裸度为 4 的树中，度为 0, 1, 2, 3 的结点数分别为 14, 4, 3, 2，求该树的结点总数 $n$ 和度为 4 的结点数，并给出推导过程。
03. 已知一裸度为 $m$ 的树中，有 $n_1$ 个度为 1 的结点，有 $n_2$ 个度为 2 的结点……有 $n_m$ 个度为 $m$ 的结点，问该树有多少个叶结点？
## 5.1.5 答案与解析
### 一、单项选择题
01. D
树是一种分层结构，它特别适合组织那些具有分支层次关系的数据。
02. A
除根结点外，其他每个结点都是某个结点的孩子，因此树中所有结点的度数加 1 等于结点数，即所有结点的度数之和等于总结点数减 1。这是一个重要的结论，做题时经常用到。
03. A
树的路径长度是指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值应是树的高度减 1。注意与哈夫曼树的带权路径长度相区别。
<!-- page: 140 -->
2027年数据结构考研复习指导
04. A
要使得具有 $n$ 个结点、度为4的树的高度最大，就要使得每层的结点数尽可能少，类似右图所示的树，除最后一层外，每层的结点数是1，最终该树的高度为 $n - 3$。树的度为4只能说明存在某结点正好（也最多）有4个孩子结点，选项D错误。
05. A
要使得度为4、高度为 $h$ 的树的总结点数最少，需要满足以下两个条件：
① 至少有一个结点有 4 个分支。
② 每层的结点数尽可能少。
情况类似右图所示的树，结点数为 $h + 3$。
要使得度为4、高度为 $h$ 的树的总结点数最多，应使每个非叶结点的度均为4，即满树，总结点数最多为 $1 + 4 + 4^{2} + \dots +4^{h - 1}$。
对于上面的两题，应画出草图来求解，就能一目了然。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
06. C
要求满足条件的树，那么该树是一棵完全三叉树。在度为3的完全三叉树中，第1层有1个结点，第2层有 $3^{1} = 3$ 个结点，第3层有 $3^{2} = 9$ 个结点，第4层有 $3^{3} = 27$ 个结点，因此结点数之和为 $1 + 3 + 9 + 27 = 40$，第5层的结点数 $= 50 - 40 = 10$ 个，因此最小高度为5。
07. D
总结点数 $n = n_{0} + n_{1} + n_{2} + n_{3} = 6 + n_{1} + 1 + 2 = n_{1} + 9$，总度数 $= n - 1 = n_{1} + 2n_{2} + 3n_{3} = n_{1} + 2 + 6 = n_{1} + 8$，根据题目条件无法得出 $n$ 的具体值，只能证明 $n$ 是一个大于或等于9的任意整数。画出满足题目条件的树，可以是右图所示的一棵树，该树中无法确定 $n$ 的具体数量。
08. D
设叶结点数为 $N_{0}$，总结点数为 $N$，则 $N = N_{1} + 2N_{2} + 3N_{3} + \dots + mN_{m} + 1$，又因为 $N = N_{0} + N_{1} + N_{2} + N_{3} + \dots + N_{m}$，所以 $N_{0} = N_{2} + 2N_{3} + \dots + (m - 1)N_{m} + 1 = \sum_{i=2}^{m}(i - 1)N_{i} + 1$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
09. B
设树中度为 $i$（$i = 0,1,2,3,4$）的结点数分别为 $n_i$，树中结点总数为 $n$，则 $n =$ 分支数 + 1，而分支数又等于树中各结点的度之和，即 $n = 1 + n_1 + 2n_2 + 3n_3 + 4n_4 = n_0 + n_1 + n_2 + n_3 + n_4$。依题意，$n_1 + 2n_2 + 3n_3 + 4n_4 = 10 + 2 + 30 + 80 = 122$，$n_1 + n_2 + n_3 + n_4 = 10 + 1 + 10 + 20 = 41$，可得出 $n_0 = 82$，即树 $T$ 的叶结点的个数是 82。
10. C
解法1：树有一个重要性质，即在 $n$ 个结点的树中有 $n - 1$ 条边，“那么对于每棵树，其结点数比边数多1”。本题森林中的结点数比边数多10（$25 - 15 = 10$），显然共有10棵树。
解法2：仔细分析后发现此题也是考查图的性质：生成树和生成森林。对于图的生成树有一个重要的性质，即图中顶点数若为 $n$，则其生成树含有 $n - 1$ 条边。对比解法1中树的性质，不难发现两种解法都用到了性质“树中结点数比边数多1”，后面的分析如解法1。
<!-- page: 141 -->
第5章 树与二叉树
129
## 二、综合应用题
### 01. 【解答】
要求含有 $n$ 个结点的三叉树的最小高度，那么满足条件的一定是一棵完全三叉树，设含有 $n$ 个结点的完全三叉树的高度为 $h$，第 $h$ 层至少有 1 个结点，至多有 $3^{h-1}$ 个结点。则有
$$
1 + 3^{1} + 3^{2} + \cdots + 3^{h-2} < n \leqslant 1 + 3^{1} + 3^{2} + \cdots + 3^{h-2} + 3^{h-1}
$$
即 $(3^{h-1} - 1)/2 < n \leqslant (3^h - 1)/2$，得 $3^{h-1} < 2n + 1 \leqslant 3^h$，即 $h < \log_3(2n + 1) + 1, h \geqslant \log_3(2n + 1)$。
因为 $h$ 只能为正整数，$h = \lceil \log_3(2n + 1) \rceil$，所这种三叉树的最小高度是 $\lceil \log_3(2n + 1) \rceil$。
### 02. 【解答】
设树中度为 $i$（$i = 0, 1, 2, 3, 4$）的结点数为 $n_i$，则结点总数 $n = n_0 + n_1 + n_2 + n_3 + n_4$，即 $n = 23 + n_4$，根据“树中所有结点的度数加 1 等于结点数”的结论，有 $n = 0 + n_1 + 2n_2 + 3n_3 + 4n_4 + 1$，即有 $n = 17 + 4n_4$。
综合两式得 $n_4 = 2$，$n = 25$。所以该树的结点总数为 25，度为 4 的结点数为 2。
### 03. 【解答】
树中的结点数等于所有结点的度数加 1，因此有 $n = \sum_{i=0}^{m} i n_i + 1 = n_1 + 2n_2 + 3n_3 + \cdots + m n_m + 1$。
又有 $n = n_0 + n_1 + n_2 + \cdots + n_m$，所以
$$
\begin{array}{l}
n_0 = (n_1 + 2n_2 + 3n_3 + \cdots + m n_m + 1) - (n_1 + n_2 + \cdots + n_m) \\
= n_2 + 2n_3 + \cdots + (m - 1)n_m + 1 = 1 + \sum_{i=2}^{m} (i - 1)n_i \\
\end{array}
$$
## 注意
综合以上几题，常用于求解树结点与度之间关系的有：
① 总结点数 $= n_0 + n_1 + n_2 + \cdots + n_m$。
② 总分支数 $= 1n_1 + 2n_2 + \cdots + m n_m$（度为 $m$ 的结点引出 $m$ 条分支）。
③ 总结点数 $=$ 总分支数 + 1。
这类题目常在选择题中出现，读者对以上关系应当熟练掌握并灵活应用。
## 5.2 二叉树的概念
### 5.2.1 二叉树的定义及其主要特性
#### 1. 二叉树的定义
二叉树是一种特殊的树形结构，其核心特征在于：每个结点至多拥有两棵子树（不存在度大于 2 的结点），且这两棵子树具有明确的左右之分，其次序是固定的，不可交换。
与树类似，二叉树也以递归的方式定义。二叉树是包含 $n$（$n \geqslant 0$）个结点的有限集合：
① 或者为空二叉树，即 $n = 0$。
② 或者由一个根结点以及两棵互不相交的被称为根的左子树和右子树构成，且左右子树本身也均为二叉树。
二叉树属于有序树。即使某个结点仅有一棵子树，也要区分它是左子树还是右子树；若交换某结点的左右子树，则会得到另一棵不同的二叉树。二叉树的 5 种基本形态如图 5.2 所示。
<!-- page: 142 -->
2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图5.2 二叉树的5种基本形态 注意，二叉树与度为2的有序树有本质区别： ① 度为 2 的树至少包含 3 个结点，而二叉树可以为空。 ② 在度为 2 的有序树中，若某结点只有一个孩子，则无须区分左右次序（因为左右关系是相对于另一个孩子而言的）；而在二叉树中，无论结点是否拥有两个孩子，其子树的左右位置都是确定且不可省略的，这种次序并非相对概念，而是结构本身的固有属性。 ## 2. 几种特殊的二叉树 1）满二叉树。一棵高度为 $h$ 且包含 $2^b - 1$ 个结点的二叉树称为满二叉树，即每一层都含有该层所能容纳的最大结点数，如图5.3(a)所示。满二叉树的所有叶结点均位于最下一层，且除叶结点外，其余每个结点的度均为2。 可对满二叉树按层序进行编号；约定根结点编号为1，自上而下，自左向右依次编号。在此编号规则下，对于编号为 $i$ 的结点，若其存在双亲，则双亲编号为 $[i/2]$；若存在左孩子，则左孩子编号为 $2i$；若存在右孩子，则右孩子编号为 $2i + 1$。 **考点击注** 完全二叉树的特性（2009、2011、2018、2025） 2）完全二叉树。高度为 $h$ 且包含 $n$ 个结点的二叉树，当且仅当其每个结点与高度为 $h$ 的满二叉树中编号为 $1 \sim n$ 的结点一一对应时，称为完全二叉树，如图5.3(b)所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 满二叉树 图5.3 两种特殊形态的二叉树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 完全二叉树 3）二叉排序树。其左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字，且左子树和右子树本身也各是一棵二叉排序树。 4）平衡二叉树。树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。关于二叉排序树和平衡二叉树的详细介绍，见本书第7.3节。 **考点击注** 正则 $k$ 叉树树高和结点数的关系的应用（2016） 5）正则二叉树。树中每个分支结点均有2个孩子，即树中仅有度为0或2的结点。