当前位置：首页 > news >正文

数据结构复习（第五章）：树与二叉树

news 2026/4/17 22:34:26

树与二叉树：从层次关系到递归结构的一整套理解

这一章讨论的主题是树与二叉树。和前面的线性表、串相比，这里的结构不再是单一的前后次序，而是开始进入层次化组织的世界。一个结点之下可以分出多个后继，不同分支之间彼此并列，而整棵结构又围绕根结点向下展开。也正因为如此，树在数据结构中有非常重要的位置：文件目录、组织关系、分类体系、表达式结构，以及后面会学到的堆、并查集、搜索树等内容，本质上都和树形组织方式密切相关。

这一章的内容主线非常清晰。先讲树的基本概念，建立结点、层次、度、叶子、路径、深度等基本术语；再过渡到二叉树，说明二叉树并不只是“度不超过 2 的树”，而是一种左右子树有严格区分的递归结构；接着讨论二叉树的顺序存储与链式存储，再进一步进入遍历问题，包括先序、中序、后序和层次遍历；最后通过由遍历序列构造二叉树等内容，把前面的定义、性质和算法真正串联起来。整体上看，这一章最核心的，不只是会背结论，而是理解“树为什么天然适合递归表示”和“遍历为什么本质上是在规定访问根结点的时机”。

一、树的本质：一种分层展开的逻辑结构

树可以看作由若干结点构成的有限集合。当结点个数为零时，它是一棵空树；当结点个数大于零时，整棵树有且仅有一个根结点，其余结点又可以分成若干个互不相交的子树。这个定义看上去简短，但里面包含了树最核心的两层含义。

第一层含义是“唯一根”。树不是任意连起来的一组结点，而必须存在唯一的起点。第二层含义是“递归分解”。一棵树去掉根之后，剩余部分并不是杂乱无章的，而是若干棵规模更小、结构相同的树。也就是说，树的定义本身就带有递归色彩，后面所有有关树的存储、遍历和性质分析，几乎都建立在这个递归结构之上。

和线性结构相比，树最明显的差别在于关系类型变了。线性表强调一对一的前驱后继关系，而树强调的是一种一对多的层次关系。父结点可以拥有多个孩子结点，孩子结点向下又可以继续分支，因此树更适合描述带层级的对象集合。

二、树的基本术语，关键在于把“位置关系”说清楚

学习树时，最先要过的是术语关。因为树中结点的意义，不只是它本身存了什么数据，更取决于它位于整棵结构中的什么位置。

结点是树中的基本单位。根结点是最顶层的那个结点，它没有前驱。结点的子树根称为该结点的孩子结点，而这个结点称为孩子结点的双亲结点。具有同一双亲的结点互称兄弟。没有孩子的结点称为叶子结点，也叫终端结点；至少有一个孩子的结点称为分支结点，也叫非终端结点。

树中一个结点拥有的子树个数称为该结点的度，树的度则是各结点度的最大值。这个概念非常重要，因为后面二叉树、m 叉树、满二叉树、完全二叉树等很多定义，都和“每个结点最多能分出多少个孩子”直接相关。

此外，层次、路径、路径长度、结点深度、树的高度这些概念也必须分清。通常把根所在层记作第一层，根的孩子在第二层，依次向下扩展。两个结点之间沿父子关系依次经过的结点序列称为路径，路径上的边数称为路径长度。一个结点的深度是从根到该结点所经历的层级，而树的高度则是树中结点层数的最大值。很多选择题和计算题，看似在换着花样提问，本质都是在问你是否把这些位置概念真正想明白。

三、树的性质，背后都是“边数、层数、分支数”的关系

树这一节最常见的一类问题，就是围绕结点总数、边数、层数和度之间的关系进行推导。真正值得掌握的不是零碎结论，而是这些结论为什么成立。

首先，树中结点数如果是 n，那么边数一定是 n−1。原因并不复杂：除根结点外，每个结点都有且仅有一个双亲，因此每增加一个非根结点，就对应增加一条从双亲到它的边。这个结论极其基础，后面会反复使用。

其次，树中所有结点的度数总和等于边数。因为每一条边都可以理解为某个双亲指向某个孩子，因此一条边恰好对应一次“度”的贡献。于是如果把所有结点的度加起来，结果恰好就是整棵树的边数，也就是 n−1。很多树的计数题，本质就是从这个角度切入的。

再往下，如果已知不同度数的结点个数，也可以建立总结点数、叶子数与分支结点数之间的关系。这类题常常会结合“某树是 m 叉树”“某树的结点度只可能为若干种值”“某层恰有多少结点”来出题。做这类题时，最稳妥的方法不是凭印象套公式，而是先把总结点数与总边数分别表示出来，再利用“边数 = 总度数 = n−1”去联立分析。

四、二叉树不是一般树的特例那么简单，而是一种更严格的结构

二叉树经常被误解为“度不超过 2 的树”。这个说法只说对了一部分。更准确地说，二叉树是另一类递归定义的结构：它或者为空，或者由一个根结点以及一棵左子树和一棵右子树组成，且左右子树本身也都是二叉树。

这里最关键的地方在于“左”和“右”不能颠倒。一般树中，孩子之间通常没有固定次序；而二叉树中，左子树和右子树是有区分的。即使某个结点只带一个孩子，这个孩子是左孩子还是右孩子，也会构成不同的二叉树。这就是为什么“二叉树并不等价于每个结点度不超过 2 的有序树”的直观根源。

正因为左右有别，二叉树才会比一般树更适合表达有方向、有顺序的结构。例如表达式树中，左子树和右子树分别对应不同运算对象；排序树中，左子树和右子树承载着不同大小关系；遍历序列中，不同访问顺序也都依赖于左右子树的严格区分。

五、几类典型二叉树，要区分的是“形状是否规整”

二叉树内部又可以分出多种典型形态，其中最常考的是满二叉树、完全二叉树，以及二叉排序树、平衡二叉树等概念中的前两种基础形态。

满二叉树指的是除叶子结点外，每个结点都有两个孩子，并且所有叶子都位于同一层的二叉树。它的结构非常规整，每一层都被填满，因此很多结论都可以直接写成按层累加的形式。若树高为 h，则总结点数为 2^h−1，第 i 层最多有 2^(i−1) 个结点，叶子结点数为 2^(h−1)。

完全二叉树则比满二叉树稍微宽松一些。它要求的是：除最后一层外，其余各层都达到最大结点数，而最后一层的结点必须从左到右连续排列。也就是说，完全二叉树允许最后一层不满，但不能中间有空缺、右边却还有结点。这个“从左到右连续”是判断完全二叉树的关键。

很多题之所以容易错，就是因为把这两个概念混在一起。满二叉树强调的是每层都满，完全二叉树强调的是编号连续、形状尽量靠左。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。只要最后一层少几个最右侧结点，它依然可能是完全二叉树，但已经不是满二叉树了。

六、二叉树最重要的性质，是按层展开后的数量规律

二叉树之所以适合出计算题，是因为它的层次结构特别规则，很多数量关系都可以直接从按层分析中推出。

第一个基本性质是：二叉树第 i 层上的结点数最多为 2^(i−1)。因为根只有一个，下一层最多 2 个，再下一层每个结点最多再分出 2 个，所以按层翻倍增长。

第二个基本性质是：高度为 h 的二叉树最多有 2^h−1 个结点。这个结论就是把每层最多结点数累加得到的结果，即 1+2+4+…+2^(h−1)=2h−1。

第三个特别重要的性质是：对于任意一棵非空二叉树，如果度为 0 的结点个数为 n0，度为 2 的结点个数为 n2，那么总有 n0=n2+1。这个结论在综合题中极其常见。它背后的原因可以从边数关系推出：设度为 1 的结点数为 n1，则总结点数 n=n0+n1+n2，而边数既等于 n−1，也等于 0·n0+1·n1+2·n2=n1+2n2，两式相等化简即可得到 n0=n2+1。这个结论几乎是解决“已知某类结点个数，求叶子数”问题的标准入口。

对于完全二叉树，还有两条经常和顺序存储结合起来的性质。其一，若总结点数为 n，则树高为 ⌊log2 n⌋+1。其二，若按层自上而下、从左到右给结点编号为 1 到 n，则编号为 i 的结点，其双亲编号为 ⌊i/2⌋，左孩子为 2i，右孩子为 2i+1。这正是顺序存储能够高效表示完全二叉树的根本原因。

七、二叉树的存储，不只是会写结构体，而是理解“结构适合哪种表示”

二叉树常见的存储方式有两大类：顺序存储和链式存储。

顺序存储通常用数组实现。它最适合完全二叉树，因为完全二叉树按层编号后基本没有空位，数组位置与逻辑结构之间能建立非常自然的对应关系。根放在下标 1 或 0 处都可以，只要约定一致，就能用简单公式求双亲和孩子位置。这样的表示访问结点非常直接，也适合一些只关心位置关系的算法。

但如果二叉树比较稀疏，顺序存储就会浪费大量空间。因为很多数组单元对应的逻辑位置其实没有结点，却仍然得保留出来。这也是为什么顺序存储通常只特别适合完全二叉树，而对一般形态的二叉树并不总是理想。

链式存储则更通用。二叉链表中的每个结点通常包括数据域、左孩子指针和右孩子指针三个部分。这样无论树是满的、完全的、偏斜的还是形状很不规则，都可以用是否为空指针来描述孩子是否存在。链式存储的优势在于结构灵活，特别适合一般二叉树的递归处理、遍历和动态构造。

从学习角度看，这里真正要掌握的是：顺序存储利用的是位置规律，链式存储利用的是指针关系；完全二叉树更偏向前者，一般二叉树更偏向后者。不要把“顺序存储二叉树”简单理解为一种默认写法，它其实是一种和树形特征高度绑定的特定表示方式。

八、遍历的本质，不是走一遍而已，而是在规定“何时访问根”

二叉树遍历是这一章的重心。很多人一开始会把先序、中序、后序背成口号，但真正理解它们的关键，是抓住一句话：三种深度优先遍历的区别，不在于左子树或右子树谁先谁后，而在于“访问根结点”的时机不同。

先序遍历是先访问根，再遍历左子树，最后遍历右子树。也就是“根—左—右”。中序遍历是先遍历左子树，再访问根，最后遍历右子树，也就是“左—根—右”。后序遍历则是先遍历左子树，再遍历右子树，最后访问根，即“左—右—根”。

三者看起来只差一步，但表达的结构信息并不一样。先序强调先看到根，因此常用于需要优先处理父结点的场景；中序把根放在左右子树之间，对于二叉排序树会得到有序序列；后序则把根放在最后，特别适合先处理子问题再合并结果的情形，比如删除整棵树、计算子树属性等。

这三种遍历都具有明显的递归特征。因为任意一棵二叉树，本身就是根、左子树、右子树的组合；只要把“遍历一棵树”的问题拆成“遍历左子树”“遍历右子树”，再在恰当时机访问根，就能自然写出递归算法。换句话说，遍历算法之所以看起来简洁，并不是因为它技巧性强，而是因为它和二叉树的定义本身完全同构。

九、层次遍历是另一种思路，它按层展开而不是沿递归深入

除了先序、中序、后序这些深度优先方式，二叉树还有层次遍历。层次遍历按照从上到下、从左到右的顺序访问结点，先访问根，再访问下一层的所有结点，再继续向下推进。

和前三种遍历不同，层次遍历的核心不在递归，而在队列。因为按层访问意味着：当访问到某个结点时，需要把它的左孩子、右孩子按顺序放到后面等待访问；而最先进入等待队列的，又应该最先被处理，这正好符合队列先进先出的特点。因此层次遍历通常和队列是绑定出现的。

从结构理解上说，层次遍历体现的是“横向展开”的思路，而先序、中序、后序体现的是“纵向递归”的思路。前者更适合描述树的整体层级，后者更适合描述子树内部的递归关系。两类遍历结合起来，基本就把二叉树最重要的访问方法覆盖完整了。

十、由遍历序列确定二叉树，关键在于谁能提供根的位置

这一章另一个非常核心的内容，是根据遍历序列构造二叉树。这里最重要的不是机械操作，而是理解不同遍历序列各自提供了什么信息。

如果给出先序序列和中序序列，就可以唯一确定一棵二叉树。原因在于：先序序列的第一个元素一定是根结点，而中序序列中根左边的部分一定属于左子树，右边的部分一定属于右子树。这样一来，左右子树的规模和内容都被划分清楚，再在对应子区间中递归处理，就能唯一恢复整棵树。

同理，如果给出后序序列和中序序列，也能唯一确定二叉树。因为后序序列的最后一个元素一定是根，接下来仍然可以借助中序序列去切分左、右子树，再递归构造。

但若只给先序和后序，一般情况下不能唯一确定一棵二叉树。因为这两种序列虽然都能指出根，却不能独立提供左右子树的分界位置，尤其当某些结点只有一个孩子时，究竟这个孩子是左孩子还是右孩子，信息会发生歧义。也就是说，真正能起到“切分左右子树”作用的是中序序列。它把根放在中间，因此天然携带左右划分信息，这正是它在构造题中地位特殊的原因。

十一、遍历相关题目的难点，不在定义，而在能否顺着结构推

二叉树遍历题常见有三类。

第一类是直接写出某棵二叉树的某种遍历序列。这类题最基本，但最容易因为看图急躁而出错。稳妥的方法不是凭感觉跳着看，而是严格按“根、左、右”或“左、根、右”的规则一层层递归展开。

第二类是已知两种遍历序列，恢复树或求第三种遍历序列。这类题本质是对“根在哪里、左右如何切分”的考查。只要抓住根在先序首位、后序末位、中序中间这一点，推导路径就会比较清楚。

第三类是把遍历和算法功能结合起来，例如统计叶子结点数、求树高、交换左右子树、判断结构相似性等。这类题往往不是单纯背遍历，而是要求在遍历过程中顺便完成某种计算。它们共同体现了一个重要事实：遍历不是目的，而是访问结构的一种方式。真正的算法任务，通常是在遍历过程中完成信息提取、归纳或更新。

十二、这一章特别适合建立递归思维

树与二叉树之所以重要，不只是因为它们本身常用，更因为它们是训练递归思维的最佳入口之一。

在线性表里，很多操作虽然也能递归描述，但顺序结构更容易用循环表达；而在树中，递归几乎是最自然的语言。定义本身是递归的，遍历是递归的，求高度、求结点数、判断相似性、交换左右子树等操作也都天然可以递归完成。因为一棵树从整体上看是一个对象，从局部上看又由若干棵更小的树组成，这种“整体与部分同构”的特性，正是递归成立的根本原因。

真正学会树，不只是记住几个名词和公式，更重要的是逐渐形成这样的结构意识：当一个问题能分解成若干个同类型的子问题，并且子问题之间界限清晰、合并关系明确时，递归往往就是最自然的解法。二叉树正好把这一点表现得非常典型。