第六章树和二叉树是很多人学数据结构时第一次被劝退的地方。前五章的线性表、栈、队列就算没太懂硬背几遍代码也能撑过考试到这一章递归、指针、遍历、线索化全搅在一起选择题开始玩文字游戏算法题也不再是照着书抄就能跑的模板。我当时复习严蔚敏《数据结构C语言版 第2版》第六章时最头疼的就是课后题没有详细思路可参考对着题目想半天也不知道自己的推导对不对。这篇博文就把第六章最常考的几类课后题整理出来不是单纯贴答案而是讲清楚每道题为什么要这么想、题眼在哪里、哪些地方最容易踩坑。如果你是期末冲刺、考研一轮复习或者自学补基础这篇内容基本覆盖了第六章所有值得刷的题型。代码部分我会用C语言给出可直接跑的完整写法计算题会把推导过程一步一步掰开保证你看完能独立重做一遍。1. 第六章的核心地位这章的课后题到底在考什么1.1 从一棵树开始知识点之间的隐藏链条树这一章和前面最大的不同是它的知识不是零散的而是一条链定义 - 性质 - 存储结构 - 遍历 - 线索化 - 树与森林 - 哈夫曼树。课后题也是按这个顺序设计的但很多同学做题时没意识到这一点结果卡在性质题上后面的遍历题和算法题全跟着崩。你可以把这条链理解成盖房子。二叉树的性质是地基比如n0 n2 1这个公式表面上看只是一道计算题实际上它是后面判断完全二叉树、推导线索树空指针数量、验证遍历结果是否正确的基础。遍历序列还原二叉树是承重墙它不单考递归理解还直接决定你能不能写出非递归遍历和线索化算法。哈夫曼树相当于最后装修它依赖前面所有概念但又有自己独立的贪心逻辑。所以刷第六章课后题别一上来就挑算法设计题做。我见过太多人跳过性质题直接写代码结果写出来的递归函数连这棵树是否合法都判断不了。1.2 课后题的四大题型分布根据我对严蔚敏教材第六章课后题的分析题型基本可以分成四类题型常见位置难度刷题重点概念与性质题选择题、判断题、简答题偏低度的计算、完全二叉树性质、二叉树性质遍历序列题应用题、综合题中等前序中序还原、中序后序还原、层序应用递归算法设计题算法设计题偏高求深度、叶子数、复制、比较、交换左右子树线索化与哈夫曼题综合题、计算题中等线索数、前驱后继、WPL、哈夫曼编码这篇文章会按这个顺序走。每一类题我都会挑最典型的几道先讲思路再给完整解答最后补充我实际刷题过程中发现的坑。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 099 n0 0 (n0 - 1) 2n0 - 1解得n0 50。总结出一个马上能用的结论完全二叉树中叶子结点数 ⌈n/2⌉。这个结论在很多求最后一个非叶子结点下标、某结点是左孩子还是右孩子的题里都能用。这类题我有一个自己的验证技巧画一棵小规模完全二叉树比如7个结点或10个结点把层序编号和叶子数公式对照一下验证通了再往题目上套。尤其是考研的同学完全二叉树的下标计算题比如第i个结点的双亲是⌊i/2⌋和性质题经常混着考把这几条公式写在草稿纸上一开始就列出来能省不少心。3. 遍历序列题前序中序还原二叉树后序直接默写3.1 还原思路找根切左右递归遍历序列还原二叉树是我认为第六章性价比最高的一类题。它表面上是画树实际上考的是对三种遍历顺序的理解前序根 - 左 - 右第一个元素是根中序左 - 根 - 右根左边全是左子树右边全是右子树后序左 - 右 - 根最后一个元素是根只要前序中序或后序中序同时给出二叉树就被唯一确定了。只有前序后序是不够的因为无法区分左右子树。还原步骤可以固化成一套操作从前序或后序中确定根结点在中序序列中找到这个根根左边是左子树的中序序列右边是右子树的中序序列根据左右子树的长度把前序或后序中的左右子树部分切出来递归地对左、右子树重复以上步骤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 B4个结点右子树中序E I C F4个结点前序去掉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 FC在中间左子树中序E I右子树中序F。前序中C后面是E I FE 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右孩子是FB的右孩子是CC的左右孩子分别是D、EF的右孩子是GG的左孩子是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忘了比较左右子树是否为空结果两棵结构不同的树被判成相等。这类题的共同套路可以总结成一个表题目递归出口递归体典型错误求深度NULL返回0max(左深, 右深) 1忘记1求叶子数NULL返回0叶子返回1左右叶子之和缺少NULL出口求结点数NULL返回0左右结点数 1多加或漏加1复制树NULL返回NULL建根递归复制左右malloc后忘记判断是否成功判断相等都NULL返回1一个NULL返回0数据相等且左右都相等只比数据不比结构建议把这几个函数在编译器里跑通一遍。我当年学的时候就是反复敲这些代码直到不用看书也能几分钟写出来为止之后做后面线索二叉树、哈夫曼树的题都轻松不少。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 1rchild直接指向中序后继若rtag 0说明右孩子存在中序后继是右子树中最左下的结点若某结点的ltag 1lchild直接指向中序前驱若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 1246集合变为 {5, 6, 7} step 25611集合变为 {7, 11} step 371118集合变为 {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 10.050.100.15集合变为 {0.15, 0.15, 0.20, 0.20, 0.30} step 20.150.150.30集合变为 {0.20, 0.20, 0.30, 0.30} step 30.200.200.40集合变为 {0.30, 0.30, 0.40} step 40.300.300.60集合变为 {0.40, 0.60} step 50.400.601.00规定左分支编码0右分支编码1也可以反过来编码会变但平均码长一样可以得到的编码结构如下A在第4步与BCD子树合并深度为2B在第2步与CD合并深度为3C、D在第1步合并深度为4E、F在第3步合并深度为2各字符的编码长度即其在哈夫曼树中的深度字符频率编码长度A0.302B0.153C0.104D0.054E0.202F0.202平均码长 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的那一刻第六章的递归题就真的拿下了。最后再说一个我在给学生答疑时反复强调的点做任何和二叉树有关的题一定要先把空树和叶子结点这两种极端情况想清楚。递归出口往往就藏在这两种情况里。把这两个边界处理到位一道算法题就成功了一半。