数据结构第六章树和二叉树：高频课后题解析与避坑指南

第六章树和二叉树，是很多人学数据结构时第一次被劝退的地方。前五章的线性表、栈、队列就算没太懂，硬背几遍代码也能撑过考试；到这一章，递归、指针、遍历、线索化全搅在一起，选择题开始玩文字游戏，算法题也不再是照着书抄就能跑的模板。我当时复习严蔚敏《数据结构（C语言版 第2版）》第六章时，最头疼的就是课后题没有详细思路可参考，对着题目想半天也不知道自己的推导对不对。这篇博文就把第六章最常考的几类课后题整理出来，不是单纯贴答案，而是讲清楚每道题为什么要这么想、题眼在哪里、哪些地方最容易踩坑。

如果你是期末冲刺、考研一轮复习或者自学补基础，这篇内容基本覆盖了第六章所有值得刷的题型。代码部分我会用C语言给出可直接跑的完整写法，计算题会把推导过程一步一步掰开，保证你看完能独立重做一遍。

1. 第六章的核心地位：这章的课后题到底在考什么

1.1 从一棵树开始：知识点之间的隐藏链条

树这一章和前面最大的不同，是它的知识不是零散的，而是一条链：定义 -> 性质 -> 存储结构 -> 遍历 -> 线索化 -> 树与森林 -> 哈夫曼树。课后题也是按这个顺序设计的，但很多同学做题时没意识到这一点，结果卡在性质题上，后面的遍历题和算法题全跟着崩。

你可以把这条链理解成盖房子。二叉树的性质是地基，比如n0 = n2 + 1这个公式，表面上看只是一道计算题，实际上它是后面判断完全二叉树、推导线索树空指针数量、验证遍历结果是否正确的基础。遍历序列还原二叉树是承重墙，它不单考递归理解，还直接决定你能不能写出非递归遍历和线索化算法。哈夫曼树相当于最后装修，它依赖前面所有概念，但又有自己独立的贪心逻辑。

所以刷第六章课后题，别一上来就挑算法设计题做。我见过太多人跳过性质题直接写代码，结果写出来的递归函数连"这棵树是否合法"都判断不了。

1.2 课后题的四大题型分布

根据我对严蔚敏教材第六章课后题的分析，题型基本可以分成四类：

这篇文章会按这个顺序走。每一类题我都会挑最典型的几道，先讲思路，再给完整解答，最后补充我实际刷题过程中发现的坑。

2. 性质与概念题：度的计算、叶子数和完全二叉树

2.1 用"度"求叶子结点数的通法

先看一道出现频率极高的题：

设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。问T中有多少个叶子结点？

这道题很多人第一反应是画图，但树的规模一大，画图就不现实了。通法是用两个恒等式：总边数 = 总度数之和，总结点数 = 总边数 + 1。

设叶子结点数为n0，度为i的结点数为ni：

• 总度数之和：1×4 + 2×2 + 3×1 + 4×1 = 4 + 4 + 3 + 4 = 15
• 总边数 = 15
• 总结点数 = 边数 + 1 = 16
• 又因为总数 =n0 + n1 + n2 + n3 + n4 = n0 + 4 + 2 + 1 + 1 = n0 + 8
• 所以n0 + 8 = 16，解得n0 = 8

答案：8个叶子结点。

这个方法的本质是：无论树长成什么样，边数永远比结点数少1，而每个结点的度恰好等于它贡献的边数。理解了这一点，任何"求叶子数"的变体题都能直接套。

2.2 证明n0 = n2 + 1：别只背结论

教材里有个重要结论：对于任何非空二叉树，叶子结点数n0等于度为2的结点数n2加1。这个结论做题时经常直接用，但它本身也是一道经典证明题。

证明思路同样靠边数关系。设二叉树中度为1的结点数为n1，总结点数n = n0 + n1 + n2。边数B有两个表达方式：

• 从下往上看：B = n - 1
• 从上往下数：每个结点的孩子数之和，B = n1 + 2n2（度为1的结点贡献1条边，度为2的贡献2条）

于是：

n0 + n1 + n2 - 1 = n1 + 2n2 n0 = n2 + 1

这里要提醒一句：这个结论只对二叉树成立。如果题目换成"三叉树"或"度为4的树"，公式就变成了n0 = 2n3 + n2 + 1，很多人考试时顺手就写了n0 = n2 + 1，直接丢分。根源在于背结论而不是推导结论。

2.3 完全二叉树的叶子结点数：奇偶性的陷阱

下面这道题是性质题里最阴的：

一棵完全二叉树有100个结点，求叶子结点数。

完全二叉树的特点是：度为1的结点最多只有1个。所以可以分情况讨论：

• 100是偶数，说明存在1个度为1的结点
• 由完全二叉树性质：n = n0 + n1 + n2，且n0 = n2 + 1
• 代入：100 = n0 + 1 + (n0 - 1) = 2n0
• 解得n0 = 50

如果结点数是奇数，比如99，那么n1 = 0，99 = n0 + 0 + (n0 - 1) = 2n0 - 1，解得n0 = 50。

总结出一个马上能用的结论：完全二叉树中，叶子结点数 = ⌈n/2⌉。这个结论在很多求"最后一个非叶子结点下标"、"某结点是左孩子还是右孩子"的题里都能用。

这类题我有一个自己的验证技巧：画一棵小规模完全二叉树，比如7个结点或10个结点，把"层序编号"和"叶子数公式"对照一下，验证通了再往题目上套。尤其是考研的同学，完全二叉树的下标计算题（比如"第i个结点的双亲是⌊i/2⌋"）和性质题经常混着考，把这几条公式写在草稿纸上一开始就列出来，能省不少心。

3. 遍历序列题：前序+中序还原二叉树，后序直接默写

3.1 还原思路：找根，切左右，递归

遍历序列还原二叉树，是我认为第六章性价比最高的一类题。它表面上是"画树"，实际上考的是对三种遍历顺序的理解：

• 前序：根 -> 左 -> 右，第一个元素是根
• 中序：左 -> 根 -> 右，根左边全是左子树，右边全是右子树
• 后序：左 -> 右 -> 根，最后一个元素是根

只要前序+中序（或后序+中序）同时给出，二叉树就被唯一确定了。只有前序+后序是不够的，因为无法区分左右子树。

还原步骤可以固化成一套操作：

1. 从前序（或后序）中确定根结点
2. 在中序序列中找到这个根
3. 根左边是左子树的中序序列，右边是右子树的中序序列
4. 根据左右子树的长度，把前序（或后序）中的左右子树部分切出来
5. 递归地对左、右子树重复以上步骤

3.2 完整例子：前序 ABDGHCEIF + 中序 GDHBAEICF

这是一道非常经典的还原题，我做一遍给你看。

第一步，找根。

前序为A B D G H C E I F，第一个元素A就是树根。到中序G D H B A E I C F里找到A，它在第5个位置，所以：

• 左子树中序：G D H B（4个结点）
• 右子树中序：E I C F（4个结点）

前序去掉A后是B D G H C E I F，前4个属于左子树，后4个属于右子树：

• 左子树前序：B D G H
• 右子树前序：C E I F

第二步，处理左子树。

左子树前序是B D G H，根是B。到左子树中序G D H B里找B，它在最后一位，所以B的左子树中序是G D H，右子树为空。

左子树前序去掉B后是D G H，这3个全是左子树的。D G H的第一个元素D是根，中序G D H中D在中间，所以G是D的左孩子，H是D的右孩子。左子树还原完成。

第三步，处理右子树。

右子树前序是C E I F，根是C。右子树中序是E I C F，C在中间，左子树中序E I，右子树中序F。

前序中C后面是E I F，E I属于左子树，F属于右子树。E I中根是E，中序E I里E在最前面，所以I是E的右孩子。F是C的右孩子。

整棵树结构出来了。然后求后序就很简单，按"左 -> 右 -> 根"走一遍：G H D I E F C A。

3.3 中序+后序怎么处理：根在后面，方向相反

中序+后序的思路一模一样，只是根从序列末尾取。比如中序B D C E A F H G与后序D E C B H G F A：

• 后序最后一个A是根，中序里A左侧B D C E是左子树，右侧F H G是右子树
• 后序前4个D E C B对应左子树，后3个H G F对应右子树
• 左子树后序D E C B，最后一个是B，中序B D C E中B在最前，说明B无左孩子，右子树中序D C E；后序D E C中最后是C，中序D C E里C在中间，所以D是左孩子，E是右孩子
• 右子树后序H G F，最后F是根，中序F H G中F在最前，H G是右子树；后序H G中最后是G，中序H G里H是左孩子
• 所以根A的左孩子是B，右孩子是F，B的右孩子是C，C的左右孩子分别是D、E，F的右孩子是G，G的左孩子是H

这类题画树时我习惯把中序序列写在纸上、用括号按"根、左、右"逐个分隔，树画完后再用前序或后序校验一遍。我之前带过不少学生，发现最常见的错误不是找错根，而是切分序列时长度数错了，比如左子树有4个结点，结果从前序里切了3个。这属于低级失误，但考试时特别常见，所以每一步切分后我都会数一下左右子树结点数加起来等不等于当前总长度。

4. 递归算法设计题：二叉链表上的经典代码不能只会背

4.1 求二叉树深度（高度）：递归的天然载体

严蔚敏教材第六章的算法设计题，有很大一部分围绕二叉链表存储结构展开。存储结构定义是：

typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;

求深度是最基础的递归题：

int Depth(BiTree T) { if (T == NULL) { return 0; } int leftDepth = Depth(T->lchild); int rightDepth = Depth(T->rchild); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; }

这段代码的正确性可以用归纳法理解：空树深度为0，非空树的深度等于左、右子树深度的较大值再加1（根那一层）。做题时建议配合画递归调用栈来理解，不要死记代码。

我经常提醒初学者一个原则：凡是以"整棵树"为对象的操作，只要满足"可以分解为左子树和右子树的相同操作"，就应该优先考虑递归。求深度、求叶子数、复制、判等，全部符合这个模式，代码写起来非常固定。

4.2 统计叶子结点数：递归出口的判断

统计叶子结点数的经典写法：

int LeafCount(BiTree T) { if (T == NULL) { return 0; } if (T->lchild == NULL && T->rchild == NULL) { return 1; } return LeafCount(T->lchild) + LeafCount(T->rchild); }

这个函数有三个出口：空结点返回0，叶子结点返回1，非叶子返回左右子树叶子数之和。核心是判断叶子结点的条件：左右孩子都为空。

容易踩的坑是把第一个出口T == NULL忘记写。没有这个出口，递归会在访问空指针时崩溃。

我见过一个很隐蔽的错法：有人把"返回1"和"返回左右之和"的顺序写反，先写了return LeafCount(T->lchild) + LeafCount(T->rchild);，再判断是否是叶子。这就导致叶子结点也会继续向下递归，空指针会返回0，结果还是对的，但递归深度凭空增加，如果树很深或特殊形状，空指针访问会出问题。这类代码面试时容易被追问，建议一开始就写规范。

类似的还有求结点总数：

int NodeCount(BiTree T) { if (T == NULL) { return 0; } return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; }

这几个函数几乎是一个模子刻出来的，理解了"递归出口 + 递归分解"，剩下的就是套壳。

4.3 复制二叉树与判断相等：两个容易一起考的题

复制二叉树，要求用原树生成一棵结构完全相同的新树：

BiTree CopyTree(BiTree T) { if (T == NULL) { return NULL; } BiTree newNode = (BiTree)malloc(sizeof(BiTNode)); newNode->data = T->data; newNode->lchild = CopyTree(T->lchild); newNode->rchild = CopyTree(T->rchild); return newNode; }

判断两棵二叉树是否相等的递归写法则如下：

int IsEqual(BiTree T1, BiTree T2) { if (T1 == NULL && T2 == NULL) { return 1; } if (T1 == NULL || T2 == NULL) { return 0; } if (T1->data != T2->data) { return 0; } return IsEqual(T1->lchild, T2->lchild) && IsEqual(T1->rchild, T2->rchild); }

这两道题放在一起看特别有意思：复制是"从根向下分配结点"，判等是"从根向下比较结点"，前者的核心是malloc之后把指针连上，后者的核心是先判断结构是否一致，再判断数据是否一致。很多同学写判等时只比较了data，忘了比较左右子树是否为空，结果两棵结构不同的树被判成相等。

这类题的共同套路，可以总结成一个表：

建议把这几个函数在编译器里跑通一遍。我当年学的时候，就是反复敲这些代码，直到不用看书也能几分钟写出来为止，之后做后面线索二叉树、哈夫曼树的题都轻松不少。

4.4 层序遍历与按层统计宽度：递归解决不了的问题

第六章算法题里还有一类非递归的，最典型的就是层序遍历和求最大宽度。层序遍历用队列实现，队列里存的是结点指针：

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 void LevelOrder(BiTree T) { if (T == NULL) { return; } BiTree queue[MAXSIZE]; int front = 0, rear = 0; queue[rear++] = T; while (front < rear) { BiTree p = queue[front++]; printf("%c ", p->data); if (p->lchild != NULL) { queue[rear++] = p->lchild; } if (p->rchild != NULL) { queue[rear++] = p->rchild; } } }

这里的要点是队列先进先出的特性天然匹配层序：根先入队，然后每出队一个结点，就把它的左右孩子依次入队。手写数组模拟队列时，要注意rear和front的更新顺序，别把入队和出队搞反。

求二叉树最大宽度（最多结点数的那一层有几个结点），最直接的做法是在层序遍历的基础上，记录每一层的结点数：

int MaxWidth(BiTree T) { if (T == NULL) { return 0; } BiTree queue[MAXSIZE]; int front = 0, rear = 0; queue[rear++] = T; int maxWidth = 0; while (front < rear) { int levelSize = rear - front; if (levelSize > maxWidth) { maxWidth = levelSize; } for (int i = 0; i < levelSize; i++) { BiTree p = queue[front++]; if (p->lchild != NULL) { queue[rear++] = p->lchild; } if (p->rchild != NULL) { queue[rear++] = p->rchild; } } } return maxWidth; }

这段代码里，levelSize = rear - front在进入每一层循环之前记录的就是当前层结点数，随后for循环一次性把整层出队，同时入队下一层所有结点。这个方法比我最初写的"二维数组逐层存"要省空间，也更符合考试要求。

5. 线索二叉树：课后题里最容易混淆的一类题

5.1 线索数为什么是 n + 1

线索二叉树是让二叉树中空闲的指针域指向遍历前驱或后继，从而加快遍历。有一道非常经典的课后题：

在n个结点的二叉链表中，有多少个空指针域？线索化之后，有多少个线索？

第一个问题：二叉链表每个结点有两个指针域，共2n个。n个结点的二叉树有n - 1条边，也就是有n - 1个指针域被孩子结点占用。所以空指针域 =2n - (n - 1) = n + 1。

第二个问题：线索化就是把这n + 1个空指针域利用起来，指向前驱或后继，因此线索数也是n + 1。

这个n + 1非常容易记错成n或者n - 1，根源在于把空指针数和占用的指针数混在一起了。我自己的记忆方法是一个极端的例子：只有一个结点的二叉树，2个指针域都是空的，两个空指针就是线索，n + 1 = 2，和直觉完全吻合。用这个例子验证，基本不会错。

5.2 中序线索树中怎么找前驱和后继

中序线索二叉树是最常考的一种，它的规则是：

• 若某结点的rtag == 1，rchild直接指向中序后继；
• 若rtag == 0，说明右孩子存在，中序后继是右子树中最左下的结点；
• 若某结点的ltag == 1，lchild直接指向中序前驱；
• 若ltag == 0，中序前驱是左子树中最右下的结点。

这里我强烈建议不要死背，而是画一棵二叉树，标出中序遍历序列，再对照着看一遍：

比如根为A、左孩子B、右孩子C，中序序列是B A C。在线索化后，B的右指针指向A，因为B在中序下的后继是A。如果B本身有右子树，那B的后继就不是A这么简单了，而是B右子树的最左下结点。

有一道常见的判断题：在中序线索二叉树中，某结点如果有左孩子，那么它的前驱一定是左子树中最右下（也就是中序遍历左子树时最后访问）的结点。这个命题是对的。理解它只需要想清楚中序遍历的顺序：先遍历左子树，左子树访问完才访问根，所以根的"上一个结点"一定是左子树里最后被访问的那个。

课后题里还会让写"求中序线索树中某结点中序后继"的算法：

typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree; ThreadNode *NextNode(ThreadNode *p) { if (p->rtag == 1) { return p->rchild; } ThreadNode *q = p->rchild; while (q->ltag == 0) { q = q->lchild; } return q; }

这段代码的逻辑就是刚才说的规则：右指针是指针就往下找最左下，是线索就直接返回。理解了这段，中序线索树的正向遍历就能用循环实现了，不用递归。

我个人复习线索二叉树时的经验是：先别急着写代码，每天花10分钟画一棵5个结点的二叉树，手工做中序线索化，把每个指针是"孩子"还是"线索"用不同颜色标出来。连续画三天，概念就非常扎实了。教材里中序线索化的完整算法比较长，但如果已经能做手工线索化，再去看那段代码就会觉得顺理成章。

6. 哈夫曼树：WPL计算与编码题目里的隐藏陷阱

6.1 构造哈夫曼树：每次选权值最小的两棵

哈夫曼树（最优二叉树）的构造规则很简单：在森林中反复选择权值最小的两棵树合并，直到只剩一棵树。但这个"权值最小"是全局最小，不是局部最小。很多人第一次做题都会在这里翻车。

看这个经典题：

有5个叶子结点，权值分别为 7, 5, 2, 4，构造哈夫曼树并求WPL。

等一下，4个权值直接说5个叶子会引起混乱。严谨一点：给定权值 {7, 5, 2, 4}。

第一步，在所有权值中选最小的两个：2和4，合并为6。此时集合变成：{7, 5, 6}。

注意！此时最小的两个是5和6，不是5和7，更不是7和6。因为6是新生成的，也必须参与下一轮比较。第二步把5和6合并为11，集合变成{7, 11}。

第三步把7和11合并为18。

所以这棵哈夫曼树的结构是：权值2和4深度为3，权值5深度为2，权值7深度为1。

WPL = (2 + 4) × 3 + 5 × 2 + 7 × 1 = 18 + 10 + 7 = 35

如果第二步错误地选了5和7合并，得到的WPL是36，比正确答案大1。这说明哈夫曼算法每次必须从当前集合选全局最小，这一步错，后面全错。

做构造题时，我建议在草稿纸上每次合并之后，把新的集合完整写出来并重新排序，这样能避免"5和7"这种错误。比如上面这道题，我习惯写成：

原始集合：{2, 4, 5, 7} step 1：2+4=6，集合变为 {5, 6, 7} step 2：5+6=11，集合变为 {7, 11} step 3：7+11=18，集合变为 {18}

这样每一步都清晰可见。

6.2 哈夫曼编码与平均码长

哈夫曼编码是哈夫曼树最直接的应用。典型题目是给出每个字符的出现频率，要求构造哈夫曼编码并计算平均码长。

字符 A、B、C、D、E、F 的出现频率分别为 0.30、0.15、0.10、0.05、0.20、0.20，求哈夫曼编码及平均码长。

把频率作为权值，重复构造过程：

初始：{0.05, 0.10, 0.15, 0.20, 0.20, 0.30} step 1：0.05+0.10=0.15，集合变为 {0.15, 0.15, 0.20, 0.20, 0.30} step 2：0.15+0.15=0.30，集合变为 {0.20, 0.20, 0.30, 0.30} step 3：0.20+0.20=0.40，集合变为 {0.30, 0.30, 0.40} step 4：0.30+0.30=0.60，集合变为 {0.40, 0.60} step 5：0.40+0.60=1.00

规定左分支编码0，右分支编码1（也可以反过来，编码会变，但平均码长一样），可以得到的编码结构如下：

• A：在第4步与BCD子树合并，深度为2
• B：在第2步与CD合并，深度为3
• C、D：在第1步合并，深度为4
• E、F：在第3步合并，深度为2

各字符的编码长度即其在哈夫曼树中的深度：

平均码长 = 0.30×2 + 0.15×3 + 0.10×4 + 0.05×4 + 0.20×2 + 0.20×2 = 0.60 + 0.45 + 0.40 + 0.20 + 0.40 + 0.40 = 2.45。

注意：哈夫曼编码的码字可能不唯一，因为每次合并时左右子树谁编0谁编1是可以任选的，但平均码长是固定的。考试如果问编码，答案对得上平均码长通常就算对，但最好画图说明编码规则。

6.3 哈夫曼树的几个易错判断

哈夫曼这块的判断题，我整理了几个高频坑：

• 哈夫曼树中没有度为1的结点。因为每次合并两棵，整棵树是满的，度为1的结点不存在。这是哈夫曼树的一条重要性质。
• 哈夫曼树不一定唯一。当存在多个相同权值时，构造出来的树形可能有区别，但WPL唯一且最小。
• 权值越小离根越远，权值越大离根越近。这是贪心策略的直接结果。
• 有n个叶子结点的哈夫曼树，总结点数是2n - 1。推导很简单：没有度为1的结点，所以n = n0 + n2，又n0 = n2 + 1，得到n2 = n0 - 1，总数n0 + n2 = 2n0 - 1 = 2n - 1。

最后一个性质在做选择题时特别有用，比如"某哈夫曼树有15个结点，问叶子结点有多少个"，根据15 = 2n - 1直接得出叶子数为8。

我记得自己第一次做哈夫曼题时，合并到第三轮就开始犯迷糊，总是忘了新生成的结点也要参与下一轮比较。后来养成一个习惯：每合并一次，就在草稿纸上把新的权值序列重新从小到大排序，再圈出前两个。这个方法一直用到考研结束，基本没有在这类题上失过分。

7. 复习建议：我在刷第六章习题时的几点体会

这一章的课后题做一遍往往不够，很多题第一遍能看懂答案，第二遍合上书还是会卡壳，尤其是递归算法设计题。我的建议是三大轮：

第一轮，按题型刷。先把性质计算题做熟，再画遍历树，再写递归代码，最后啃线索树和哈夫曼。不要一上来就混合刷，容易把自己绕晕。

第二轮，限时刷。每道算法题给自己10到15分钟。超时就看答案，看完合上书自己再写一遍。这一轮的目标不是"看懂"，而是"能默写"。

第三轮，只做标记过的错题和难题。我当时会在题目旁边用铅笔标难度，三轮复习时只看两星以上的。

代码题有个小技巧：把求深度、求叶子数、复制树、判等这四段代码放在同一个C文件里反复编译运行，用一段最简单的输入测试它们。相信我，当你亲手调通"复制出来的树和原树判等返回1"的那一刻，第六章的递归题就真的拿下了。

最后再说一个我在给学生答疑时反复强调的点：做任何和二叉树有关的题，一定要先把空树和叶子结点这两种极端情况想清楚。递归出口往往就藏在这两种情况里。把这两个边界处理到位，一道算法题就成功了一半。