树和二叉树习题全攻略：性质、遍历与哈夫曼编码详解

说实话数据结构里最容易劝退初学者的章节第六章“树和二叉树”绝对排得上号。前面五章你还能靠画图、写循环把顺序表、链表、栈和队列熬过去一到树这里递归、遍历、性质推导、哈夫曼树全部涌上来很多人学着学着就开始怀疑人生。期末考试临近时后台问我第六章习题答案的人特别多所以我干脆把这一章的课后习题按知识点重新梳理了一遍把高频考点的答案、推导过程和算法设计题的可运行代码都写出来帮大家把这章彻底拿下。这份整理覆盖了概念辨析、性质应用、遍历序列还原、核心算法设计题、哈夫曼树与编码这几个大方向基本对应严蔚敏这本教材第六章课后习题的主要题型。不论你是期末突击、考研复习还是自学被习题卡住了都可以直接对照参考。提示一下不同年份印次的教材习题编号略有差异所以我没有逐题按原书编号罗列而是按“考点类型”归类讲解这样对谁都适用。1. 开篇把框架理清先搞懂树再谈做题做过几道树习题的人应该都有体会很多题不是不会算而是对概念的理解模棱两可导致一换条件就翻车。所以我建议先花二十分钟把基础框架的细节抠清楚再去做题。1.1 树、二叉树、完全二叉树、满二叉树到底哪里不同“树”是n个结点的有限集合这个大家都能背。但真正做题时几个兄弟概念经常被拿来挖坑。二叉树是每个结点至多有两棵子树且子树有左右之分次序不能颠倒。注意“至多”两个字意味着一个结点的度可以是0、1或2三种情况都合法。树则没有左右之分这个概念结点可以有多个孩子。满二叉树深度为k的二叉树如果结点总数恰好是2^k - 1每一层的结点数都达到最大值就是满二叉树。完全二叉树深度为k、有n个结点的二叉树当且仅当它的每一个结点都与深度为k的满二叉树中编号1到n的结点一一对应时称为完全二叉树。白话讲就是结点从左到右、从上到下连续排列中间不能有空缺。一个很容易踩坑的点满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。比如深度为3的完全二叉树可以有5个结点、6个结点、7个结点只有7个结点时才同时是满二叉树。另一个必须记牢的结论是完全二叉树中度为1的结点个数要么是0要么是1。这是因为完全二叉树在最后一层只可能从右向左连续缺失结点倒数第二层只可能从右向左缺少右孩子不会出现某个结点的右孩子存在而左孩子不存在的情况。这个结论在求结点数的题里经常用到后面应用题会展示用法。树的存储结构也要分清双亲表示法适合反复找父节点孩子表示法适合找孩子孩子兄弟表示法二叉树表示法可以把任何一棵树转换成二叉树处理。这个转换关系在很多习题里是隐含条件遇到“树转二叉树”的题时记住“左孩子右兄弟”这六个字就够了。1.2 三条经典性质做题时最常用的那几条公式二叉树的性质是第六章习题的“题眼”一半以上的概念题和应用题最终都落在公式上。我挑了三条最高频的每一条都建议自己推一遍光背容易忘。性质一二叉树的第i层上至多有2^(i-1)个结点i≥1。这个用等比数列就能推第1层最多1个第2层最多2个第3层最多4个。归纳法写出来很简洁考试时如果忘记现场画三层树也能推回来。性质二深度为k的二叉树至多有2^k - 1个结点k≥1。这就是等比数列求和1 2 4 ... 2^(k-1) 2^k - 1。注意区分“第k层最多”和“深度为k的整个树最多”前者是2^(k-1)后者是2^k - 1选择题特别爱在这里制造混淆。性质三对任何一棵非空二叉树如果叶子结点数为n0度为2的结点数为n2则n0 n2 1。这个性质的推导要会写因为它不只是结论本身那么简单推导过程还体现了“边和结点之间的数量关系”这种通用思路。设树中总结点数为n度为1的结点数为n1。一方面n n0 n1 n2另一方面从边的角度看除根结点外每个结点都有一条边进入所以边的总数等于n - 1同时也等于n1 2 * n2。于是有 n0 n1 n2 - 1 n1 2n2化简得到 n0 n2 1。这条公式碰到“求叶子结点数”的题几乎是必用的。比如题目说“一棵二叉树有度为2的结点15个”那叶子结点数就是16个。如果题目问“度为2的结点数为20度为1的结点数为10总结点数是多少”那就先算n0 21再算n 21 10 20 51。2. 概念题答案判断、选择、填空里反复出现的坑概念题看似送分其实是整章失分的重灾区。很多错误选项设计得相当刁钻每一个都踩在定义的模糊地带。2.1 判断题高频考点逐条分析我把教材和各类试卷里出现频率最高的几道判断题拿出来逐一说结论和理由。第一题“二叉树是度为2的树。”这句话是错的。二叉树有左右子树之分而“度为2的树”没有这个约束一棵度最大的结点有两个孩子的树如果两个孩子地位对调仍视为同一棵树那它就不是二叉树意义上的树。换句话说二叉树不是“度为2的树”的特例两者是不同定义体系下的概念这是最经典的认知误区。第二题“满二叉树就是完全二叉树。”前半句对后半句反过来不对。因为完全二叉树只要求结点连续排列并不要求每一层都满所以满二叉树是完全二叉树完全二叉树不一定是满二叉树。命题本身只说前半句那是对的。第三题“完全二叉树中度为1的结点最多有1个。”这个正确。最后一层结点连续缺失只能从右边开始所以倒数第二层不会同时出现两个缺少右孩子的结点度数为1的结点数至多一个。这个结论在应用题里极其好用。第四题“先序遍历序列和中序遍历序列相同的二叉树一定没有左子树。”正确。先序是“根左右”中序是“左根右”序列一旦相同左子树部分必须为空剩下的结点序列满足根在前、右子树的结点按先序排列中序时根左侧没有结点所以右子树同样可以为空或只有右子树。第五题“哈夫曼树中权值越大的叶子离根越近。”正确。哈夫曼树的构造过程每一步都选择当前最小的两个权值合并这意味着权值大的结点会在较晚的步骤才被合并从而停留在离根较近的位置。这种判断题的应对策略很简单每个选项都要回到定义和性质去核对尤其是“一定是”“至多”“至少”这类绝对化表述绝大多数时候它们在挖坑。2.2 已知条件求结点数性质应用题怎么套公式应用题中有一类非常经典给定总结点数求叶子结点数。我们在1.2节已经铺垫了公式这里直接上两个完整例子。第一题一棵完全二叉树有1001个结点求叶子结点数。解设度为0、1、2的结点数分别为n0、n1、n2。根据性质三n0 n2 1。同时总结点数满足 n0 n1 n2 1001。两式联立可得 2n0 n1 - 1 1001也就是 2n0 n1 1002。因为1002是偶数而2n0是偶数所以n1必须是偶数。完全二叉树中n1只能是0或1因此n1 0。于是2n0 1002n0 501。答案叶子结点数为501。第二题一棵完全二叉树有700个结点求叶子结点数。同样列式子2n0 n1 701因为n0 n1 n2 700n0 n2 1。这次701是奇数所以n1必须是奇数完全二叉树里只能取n1 1。所以2n0 1 701n0 350。答案叶子结点数为350。这两道题放在一起对比正好展示了n1取0还是取1的判断逻辑——结合总结点数的奇偶性来判断。我第一次学的时候总记反后来找到规律总结点数为奇数时n10总结点数为偶数时n11。你可以自己再验算一遍能明显感受到这个规律在这类题里多么省时间。3. 遍历与还原从序列到二叉树的完整流程遍历是第六章的操作核心。先序、中序、后序、层次四种遍历前三种用递归或栈层次遍历用队列。课后习题从手推遍历序列到写遍历算法都有而且经常出现“给两个遍历序列还原一棵二叉树”的题型。3.1 三种遍历的递归顺序与特点我先用一句话总结三种深度优先遍历先序是“根左右”中序是“左根右”后序是“左右根”。这里的“先、中、后”指的是根结点被访问的时机。先序遍历的特点序列的第一个结点一定是整棵树的根结点。这一点是还原二叉树的突破口。后序遍历的特点序列的最后一个结点一定是整棵树的根结点。同理可用于还原。中序遍历的特点根结点把序列分成两部分左半部分是左子树的中序序列右半部分是右子树的中序序列。这个“分界线”性质是还原二叉树的另一个核心突破口。层次遍历的特点是按层从左到右输出可以非常直观地检查二叉树的结构。它没法直接看出子树之间的递归边界但配合完全二叉树的编号规则用处很大。写递归遍历的代码时只需要记住一个框架对当前结点做什么操作然后递归进入左子树再递归进入右子树。先序、中序、后序只是三行代码的排列顺序不同。void PreOrder(BiTree T) { if (T ! NULL) { printf(%c , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } } void InOrder(BiTree T) { if (T ! NULL) { InOrder(T-lchild); printf(%c , T-data); InOrder(T-rchild); } } void PostOrder(BiTree T) { if (T ! NULL) { PostOrder(T-lchild); PostOrder(T-rchild); printf(%c , T-data); } }每次递归调用都相当于处理一棵更小的子树边界条件是当前结点为空直接返回。这个边界条件的写法是最容易被忽略的后面第6部分我会专门讲。3.2 由先序中序还原二叉树手把手推一遍这类题的完整名称是“由先序遍历序列和中序遍历序列唯一确定一棵二叉树”。为什么可以唯一确定先序第一个结点是根中序序列用根把左右子树切分开然后在左右子树中重复这个过程每一步信息都完整没有二义性。我用一个具体例子演示。设一棵二叉树的先序序列为 ABDGHCEFI中序序列为 GDHBAECIF还原整棵树。第一步先序的第一个结点是A所以A是根。第二步在中序序列 GDHB A ECIF 中找到AA左侧是GDHB属于左子树A右侧是ECIF属于右子树。第三步回到先序序列A后面紧跟的结点按顺序属于左子树。左子树的中序序列有4个结点那么先序序列中A后面的4个结点BDGH就是左子树的先序序列左子树先序为BDGH中序为GDHB。同理剩下CEFI是右子树的先序序列中序为ECIF。第四步对左子树先序BDGH的第一个结点是B中序GDHB中B在最后因此B的左子树中序为GDH右子树为空。再看左子树先序DGH根为D中序GDH中D在中间左子树是G右子树是H。于是左子树成型。第五步对右子树先序CEFI根为C中序ECIF中C在中间位置但注意C的左侧是E右侧是IF所以E是C的左孩子右子树的先序和中序分别是FI和IF。先序FI根为F中序IF说明F的左子树是I右子树为空。最后得到的树A为根左孩子B右孩子CB的左孩子DB的右孩子为空D的左孩子GD的右孩子HC的左孩子EC的右孩子FF的左孩子IF的右孩子为空这个还原过程用递归理解最顺畅建议每还原一步就把序列划掉一部分看剩下的子序列是否对应一棵完整的子树。3.3 由中序后序还原二叉树思路与易错点由中序和后序还原的套路和先序中序本质一样只是根结点要从后序序列的最后一个位置取。后序是“左右根”最后一个结点就是根。经典易错点是拿到后序序列后不少人习惯从左往右看结果把最后一个结点忽略了导致第一步就出错。正确做法是先定位后序序列末尾的根再用中序序列划分左右子树然后回到后序序列中按子树结点个数切分后序序列左右两段。再举一个例子中序序列为 GDHBAECIF后序序列为 GHDBEIFCA。后序最后一个是A所以A是根。中序中A左侧GDHB是左子树右侧ECIF是右子树。左子树在后序序列中对应前4个结点GHDB右子树对应EIFC然后再对每个子树递归处理。整个过程和前一种方法对称练一道题就能掌握。还有一类“已知先序和后序求中序”的题结论是如果不包含空结点信息一般不能唯一确定二叉树。原因是先序后序只能确定父子关系无法区分左右子树。考试中如果遇到这类的判断或简答回答“不能唯一确定”即可。4. 算法设计题这些代码题考试几乎必考第六章课后题的算法设计题基本上围绕“求深度、求结点数、求叶子数、交换左右子树、判断相似、层次遍历”展开。这些代码大题分值高而且代码量不大非常适合考前集中突破。4.1 高度、结点数、叶子数递归三板斧求二叉树高度的递归写法非常符合直觉一棵树的高度等于左、右子树高度的较大值加1。边界条件是空树高度为0。int TreeDepth(BiTree T) { if (T NULL) return 0; int leftDepth TreeDepth(T-lchild); int rightDepth TreeDepth(T-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }为什么这样写正确因为每个结点的深度等于其父结点深度加1从根往下递归时树的整体高度就是所有结点深度中的最大值。用分治思想看左子树高度和右子树高度都在递归中被计算出来取较大值再加上根结点这一层即可。求结点总数也一样简洁左子树结点数 右子树结点数 1根结点。int CountNodes(BiTree T) { if (T NULL) return 0; return CountNodes(T-lchild) CountNodes(T-rchild) 1; }求叶子结点数时关键是在递归过程中判断“当前结点是否为叶子”左右孩子都为空则返回1否则继续递归累计。int CountLeaves(BiTree T) { if (T NULL) return 0; if (T-lchild NULL T-rchild NULL) return 1; return CountLeaves(T-lchild) CountLeaves(T-rchild); }这三个函数的模板高度统一建议放在一起对照记忆。实际考试时只要把“对当前结点做什么处理”想清楚代码基本不会错。4.2 左右子树交换与相似性判断交换二叉树所有结点的左右子树是一道经典的递归操作题。思路是从根开始先交换当前结点的左右孩子再递归处理左子树和右子树。void SwapLeftRight(BiTree T) { if (T NULL) return; BiTree temp T-lchild; T-lchild T-rchild; T-rchild temp; SwapLeftRight(T-lchild); SwapLeftRight(T-rchild); }这里有一个容易忽略的细节递归调用必须放在交换之后。因为先交换了当前结点的左右孩子如果递归调用放在交换之前那递归时处理的是原来的左子树交换后原来的右子树就没有被处理。很多同学代码写出来等价于只交换了根结点的孩子就是这个顺序问题。判断两棵二叉树是否相似的思路也很有代表性两棵树都为空相似一棵为空另一棵不为空不相似否则递归判断它们的左子树是否相似、右子树是否相似。int Similar(BiTree T1, BiTree T2) { if (T1 NULL T2 NULL) return 1; if (T1 NULL || T2 NULL) return 0; return Similar(T1-lchild, T2-lchild) Similar(T1-rchild, T2-rchild); }这个题的关键是把“相似”这个语义翻译成递归条件。“相似”只要求结构相同不要求结点数据相同所以比较时完全不碰data域。写代码前先想清楚语义比直接动手写更重要。4.3 层次遍历的队列实现层次遍历要求按层从上到下、从左到右访问这天然符合队列的先进先出特性。算法流程是根结点入队队不空时出队一个结点并访问然后把它的左右孩子依次入队。#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; } } }这个队列实现使用的是数组模拟循环队列实际上就是顺序队列因为二叉树的结点不会无限增加数组大小MAXSIZE在考试范围内够用。实际工程代码里更推荐用链队列但考试手写阶段数组版本更快、更直观。层次遍历有一个常见变体按照层次分行输出每层输出后换行。实现时需要额外记录当前层的结点数和下一层的结点数或者用两个队列轮换。这个变体在很多习题和机试中出现建议有余力时自己动手写一遍。4.4 一条更综合的练习输出根到叶子的全部路径这道题综合了递归、回溯和路径记录的思路在课后习题里属于进阶题但掌握它对理解递归过程有很大帮助。题目要求输出从根到每个叶子结点的完整路径。实现思路是维护一个路径数组path递归进入某个结点时把结点加入path如果是叶子结点就输出path数组否则继续递归其左子树和右子树。递归返回后要把该结点从path中移除这就是回溯。void PrintPath(BiTree T, char path[], int pathLen) { if (T NULL) return; path[pathLen] T-data; if (T-lchild NULL T-rchild NULL) { for (int i 0; i pathLen; i) { printf(%c , path[i]); } printf(\n); } else { PrintPath(T-lchild, path, pathLen); PrintPath(T-rchild, path, pathLen); } }这里pathLen的传递方式是值传递每个递归分支都有独立的pathLen所以不需要显式回溯。如果改成指针传递就必须在递归返回后减一否则路径会残留。两种写法都对但后一种更容易出错建议考试时用值传递省心。这类题的价值在于它把“递归过程中沿途记录信息”这个能力练出来了后面学到图的最短路径、回溯算法时会觉得非常熟悉。5. 哈夫曼树与编码构造流程与WPL计算哈夫曼树是第六章另一个必考大题。它的应用场景很直观在数据压缩中让出现频率高的字符用短编码频率低的字符用长编码从而让整体编码长度最短。5.1 哈夫曼树构造过程详解含WPL手算我拿一个经典例子说明。假设有6个叶子结点权值分别为2、3、4、7、8、9请构造哈夫曼树并求WPL。构造规则只有一句话每次从森林中选两个权值最小的结点合并成一个新结点新结点的权值等于两者之和。重复这个过程直到森林中只剩一棵树。第一轮最小的是2和3合并得到5。森林变为4、5、7、8、9。第二轮最小的是4和5合并得到9。森林变为7、8、9、9。第三轮最小的是7和8合并得到15。森林变为9、9、15。第四轮两个9合并得到18。森林变为15、18。第五轮15和18合并得到33。构造完成。最终树的结构是根33左孩子15右孩子1815的孩子是7和818的孩子是9原始结点和9合并结点这个合并结点9的孩子是4和55的孩子是2和3。WPL有两种算法考试时看哪种顺手用哪种。第一种是最直接的定义叶子结点的权值乘以它到根的路径长度再求和。本例子各叶子深度分别是2和3深度44深度37和8深度2原始9深度2。所以 WPL 2×4 3×4 4×3 7×2 8×2 9×2 8 12 12 14 16 18 80。第二种算法更省事哈夫曼树的WPL等于所有非叶子结点的权值之和。本例子中所有非叶子结点的权值为5、8等等这里要按构造结果来看。等一下让我重新用第二种方法验证。构造过程中产生的非叶子结点权值是5、9、15、18、33它们之和是5 9 15 18 33 80。和第一种方法结果一致。这个性质很好用因为构造过程中每合并一次就把新结点的权值累加到一个变量里最后这个变量就是WPL代码实现起来非常顺畅。注意合并顺序不是唯一的。如果出现权值相同的结点不同的合并策略可能构造出形态不同的哈夫曼树但WPL一定是相同的。考试阅卷时通常不会严格要求树的形态一致WPL算对就能得分。5.2 哈夫曼编码规则与平均码长哈夫曼编码是在哈夫曼树上给每条边分配二进制编码通常约定左子树为0右子树为1。从根到某个叶子结点路径上的0/1序列就是该叶子对应字符的编码。用上面的树计算编码7对应左左008对应左右01原始9对应右左104对应右右左1102对应右右右左11103对应右右右右1111。每一步都符合“前缀编码”的要求没有任何一个编码是另一个编码的前缀所以可以无歧义解码。平均码长 WPL / 所有叶子权值之和 80 / (2 3 4 7 8 9) 80 / 33 ≈ 2.42字节/字符。如果直接用等长编码6个字符至少需要3位二进制位平均码长是3所以哈夫曼编码省了约19%的空间。课后题经常考“给定字符及其频率设计哈夫曼编码并求平均码长”流程就是列权值、构造哈夫曼树、标左0右1、写出每个字符的编码、套平均码长公式。每一步都比较机械练两道题就能熟练掌握。还有一个常考的概念题为什么哈夫曼编码能够保证无歧义答案是哈夫曼树的所有叶子结点都是叶子不存在某个编码是另一个编码前缀的情况这种编码叫前缀编码。教材里反复强调这一点考试简答可能直接考。6. 考试踩坑记录这些细节至少要读两遍这一章习题做错很多时候不是概念不懂而是细节处理不到位。我把实际教学中学生最常犯的几类错误整理出来考前过一遍非常有用。6.1 递归边界条件错在哪递归边界条件的错误是算法设计题失分的头号原因常见的有两种。第一种是忘记判空就访问结点字段。比如在求深度的函数里写int TreeDepth(BiTree T) { return TreeDepth(T-lchild) TreeDepth(T-rchild) ? TreeDepth(T-lchild) 1 : TreeDepth(T-rchild) 1; }这样写T为空时会继续访问T-lchild直接对空指针解引用程序必然崩掉。所有二叉树递归函数的第一步都应该是判空。第二种是返回条件写反。比如求叶子数的函数有人写成if (T-lchild NULL T-rchild NULL) return 0;这样叶子结点被计入0最终结果全错。叶子结点应该返回1非叶子才继续递归。这类错误只要在写完后手工模拟一棵只有根结点的树基本都能检查出来。6.2 数组顺序存储二叉树的下标陷阱顺序存储二叉树时如果根结点下标从0开始左孩子下标是2index 1右孩子是2index 2如果根结点下标从1开始左孩子是2index右孩子是2index 1。这个差异是填空题的经典陷阱。相关的另一个易错点是判断某个下标结点是否为叶子。需要先判断左孩子下标是否越界再判断右孩子下标是否越界两个都越界才是叶子。很多同学只判断一个就下结论正好中了出题人的圈套。完全二叉树的顺序存储还有一个高频考点编号为i的结点的双亲编号是i/2向下取整。结合这个性质可以用数组下标快速判断两个结点是否在同一层、是否为祖先关系。6.3 答题时容易被忽略的得分点简答题里画图题要注意左右子树不能画反。比如给先序中序还原二叉树画出树之后最好再用后序遍历验证一遍确认后序序列和题目一致这一步能挽回不少粗心分。算法题里如果题目要求“写出算法思想”不要一上来就贴代码。先用两三句话说明思路比如“利用递归空树高度为0否则高度为左右子树最大高度1”这体现了对算法的理解是重要得分点。还有一类应用题是“试写出中序遍历的非递归算法”这属于栈的应用。用栈模拟递归先不断把左孩子入栈然后出栈访问结点再转向右子树。这个考点经常以代码填空或手写代码的形式出现建议专门练一遍不要只背递归写法。在实际批改作业时我发现很多同学概念和性质都背得挺熟一到手写算法就暴露问题。如果你现在正处在“看书都能看懂合上书写不出来”的阶段别慌这很正常。我自己的经验是先别看答案在草稿纸上用一棵三层小树手动跑一遍递归过程把函数调用栈画出来循环几次之后再动手写代码就会自然很多。第六章的核心不是背下某一道题的答案而是建立“树递归结构”这种思维定式一旦建立起来很多题目看着都像同一个套路。