做408真题做到数据结构部分2010年第6题是一道绕不开的哈夫曼树判断题——四个选项全是性质描述没有一个需要你现场构建整棵树但当年不少人在D选项上翻了车。题目大意是对nn≥2个权值均不相同的字符构造成哈夫曼树判断下面四个叙述中哪一个是错误的。表面看是考性质记忆实际上考的是你对哈夫曼树构造过程的理解深度为什么最小两个结点互为兄弟为什么树中没有度为1的结点权值最小的两个结点是不是一定最深这些如果只靠背结论D选项就很容易选错。这道题适合两类人反复琢磨一类是正在刷408历年真题的考研党另一类是学数据结构时对哈夫曼树只停留在画树算WPL阶段的同学。把这一题吃透等价于把哈夫曼树这个考点最核心的几个性质全部过了一遍后面再做编码、前缀码、WPL计算相关的题都会顺很多。1. 先还原题目2010年第6题是一道性质判断题1.1 题目原文常见版本与考点定位2010年408统考数据结构部分的第6题题干和选项在许多复习资料里都有收录常见版本如下对nn≥2个权值均不相同的字符构造成哈夫曼树下列关于哈夫曼树的叙述中错误的是 A. 权值最小的两个结点互为兄弟 B. 树中一定没有度为1的结点 C. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 D. 权值最小的两个结点一定是最深离根最远的两个结点官方标准答案是D。注意题干里有几个限定词n≥2、权值均不相同、字符。前两个条件很关键——n≥2保证了树至少有3个结点权值均不相同是为了避免一开始就有两个初始权值相等的叶子造成直接并列后面你会发现这个限定条件对选项D的理解特别重要。这道题在当年的试卷里属于基础概念辨析题难度不算大但区分度不低。它不像画哈夫曼树或求WPL那样有明确的运算过程四个选项都是判断句每个说法看起来都挺对出题人就是要在这种看起来都对的选项里埋一个需要你抠细节的坑。1.2 这道题想考察的东西很多同学把哈夫曼树当计算题复习重点练WPL和编码忽略了它的性质推导。这道题恰恰就是用来检验你是否真正理解哈夫曼树的构造逻辑的哈夫曼树是什么是带权路径长度最短的二叉树。怎么构造每次从森林中取两棵根结点权值最小的树合并。这两句话就是全部考点的来源。A选项考第一次合并的必然性B选项考合并次数和结点数的关系C选项考合并顺序导致的权值分层规律D选项则是把权值小的离根远这个直观印象加以绝对化看你有没有意识到最深和权值最小的两个之间不是简单的一一对应。所以这一题本质上不是考记忆而是考你能不能从构造过程中推出这些性质并且判断哪些推论是安全的、哪些推论是过度的。2. 哈夫曼树的构建逻辑读懂算法再看选项2.1 为什么每次都要挑权值最小的两棵哈夫曼树的目标是让带权路径长度WPL最小。直观上讲权值大的结点应该离根近走的路径短权值小的结点应该往深处放这样总的路径加权和才小。但应该往深处放不是直接把权值按从小到大排列成一条链那样长的路径会给中间结点带来额外代价。正确的做法是自底向上合并每次挑当前森林里权值最小的两棵树把它们合并成一棵新树新树的根权值等于两者之和然后放回森林继续比较。可以把这个过程理解成把最不重要的先打包。想象你有一堆不同重量的箱子要搬上楼最重的箱子你希望少搬几层轻的箱子多搬几层不心疼。哈夫曼树做的就是先把最轻的两个箱子捆成一个大箱子然后再在剩下的箱子里找最轻的两个捆循环到最后只剩一个大箱子。每次捆出来的大箱子就是内部结点它的重量等于里面所有小箱子的重量和。这里有一个容易忽略的点合并之后产生的新结点权值不一定比剩下的所有结点都大。举例来说权值序列是{1,2,4,5}第一次合并1和2得到权值3的新结点此时森林里有3、4、53仍然是最小的所以下一步还要拿这个新结点和4合并。也就是说早期合并出来的小树会反复参与合并这就解释了为什么权值最小的两个结点通常会处在一个比较长的路径上。2.2 一个完整构建示例与WPL手算技巧拿一组权值{2,3,4,7,11}来做完整构建这组数据足够体现哈夫曼树的全部特征第一次合并取出2和3合并成权值为5的新结点。 第二次合并当前森林里是4、5、7、11取出4和5合并成9。 第三次合并当前森林里是7、9、11取出7和9合并成16。 第四次合并当前森林里是11和16合并成根结点27。完整结构是根27左孩子11右孩子1616的左孩子7右孩子99的左孩子4右孩子55的左孩子2右孩子3。看这个结构2和3在最底层深度为3从根往下数边数根深度为04的深度也是3不对仔细看4和5是9的孩子9是16的孩子16是根27的孩子所以4的深度是3根27深度016深度19深度24深度35深度32和3深度4。刚才说的结构里5下面还有2和3所以5是内部结点。重新写清楚9的左孩子4右孩子55的左孩子2右孩子3。那么2、3深度是44深度是35深度是27深度是211深度是1。WPL计算WPL2×43×44×37×211×181212141157。这里分享一个我比较推荐的手算技巧不用每次都先画完整树再数深度直接按合并顺序累加本次新结点的权值所有合并轮次的新结点权值加起来就等于WPL。以上面例子为例轮次取出的两棵树新结点权值累加和12、35524、591437、91630411、162757累加结果57和直接按深度算完全一致。这个技巧的原理在于每棵叶子的权值经过的路径长度恰好等于它每次作为某个内部结点的组成部分被向上带一层的次数把所有内部结点权值求和就等价于把每条路径上的代价都统计了一遍。2.3 从构建过程能直接看出的两条性质第一个性质树中一定没有度为1的结点。这个从合并过程看非常直接——每次合并都是拿两棵树的根作为孩子生成一个新的双分支结点整个过程只会产生度为2的内部结点和度为0的叶子不可能出现只有左孩子或只有右孩子的情况。反过来如果一棵二叉树有n个叶子且所有内部结点度都为2那么总结点数是2n-1。哈夫曼树就是这类二叉树所以以后看到哈夫曼树有n个叶子所以总结点数一定是2n-1这类说法可以直接用。第二个性质越靠近根结点权值越大。因为每次合并都取当前最小的两棵所以先合并出来的结点权值小后合并的结点权值大。一个内部结点生成后它可能作为较小的一方继续参与合并也可能被一个更大的结点合并但整体趋势一定是合并时间越晚结点越靠近根权值也越大。于是就有了任一非叶结点的权值不小于它的孩子这个结论。这两个性质在判断题里出现的频率非常高而它们都可以在30秒内从构造过程里推出来不需要单独背。3. 四个选项逐个拆解3.1 A项最小两个互为兄弟的必然性A选项说权值最小的两个结点互为兄弟这是正确的原因相当朴素第一次合并森林里全是叶子算法必须挑权值最小的两个而权值最小的两个叶子都在森林里所以它们俩必然在第一轮被合并且成为兄弟。有一个容易想多的地方如果后续合并中出现了权值相等的情况可能会有不同的合并选择但第一次合并时还没有任何内部结点不存在选新结点还是选旧结点的问题所以最初的两个最小叶子一定互为兄弟。这个结论不受哈夫曼树不唯一的影响。3.2 B项树中无度为1的结点B选项说树中一定没有度为1的结点刚才已经说过这是合并策略的必然结果。每次合并都是把两棵树拼接到一个新结点上新结点度为2两个孩子可以是叶子也可以是内部结点但绝不会出现某个结点只有一个孩子的情况。这个选项还可以用另一种方式验证n个字符对应n个叶子构造过程要合并n-1次每次合并减少一棵树最终森林里只剩一棵树。n-1次合并产生n-1个度为2的结点加上n个叶子总结点数2n-1。如果存在度为1的结点内部结点总数就不对了。所以B也正确。3.3 C项非叶结点权值与下一层的关系C选项说树中任一非叶结点的权值一定不小于下一层任一结点的权值这个表述的正确性要结合构建顺序来理解。先看同一个子树内部非叶结点的权值等于它两个孩子权值之和当然大于等于任意一个孩子而它的孩子如果要继续向下延伸下一层的结点权值也不会超过孩子本身所以自上而下权值递减在每一条路径上是成立的。再跨分支看虽然不同分支上同一层的两个结点不一定有直接的大小关系但哈夫曼算法的贪心顺序保证了后合并的结点权值更大而层数越靠近根往往对应合并时间越晚。因此在一个哈夫曼树里下面层的结点权值整体不会超过上面层的结点权值。这个性质在选择题里常被用来判断选项正误考试时候不必纠结下一层任一结点这种大范围表述按教材结论记即可。3.4 D项为什么官方判它是错的D选项说权值最小的两个结点一定是最深离根最远的两个结点官方答案是D也就是说这个说法是错误的。问题出在两个地方。第一哈夫曼树不唯一。当合并过程中出现相同权值的结点时取哪两棵合并会有不同选择树的形态会跟着变化深度分布也可能不同。第二最深的两个这个说法暗示最深层只有两个结点但实际构造中完全可能出现多片叶子并列在同一深度的情况。举个可以口算的例子权值序列{49,50,52,53,54,55}。第一步495099第二步5253105第三步5455109。此时森林里是99、105、109第四步99105204第五步109204313。最终树形是根313左孩子109右孩子204204的左孩子99右孩子10599下面是49和50105下面是52和53109下面是54和55。算深度49、50深度是352、53深度也是354、55深度是2。也就是说最深层不止49和50两个结点52和53同样位于最大深度。这时候说权值最小的两个结点一定是最深的两个结点就不够严谨——它们虽然位于最大深度但并不是唯一最深的两个。如果你还觉得这个例子只是并列不算真正推翻那可以从出题角度来看D选项里一定这个词在408选择题里几乎就是错误选项的信号。一个性质如果只在部分情况下成立就不能说一定。哈夫曼树的形态多样、深度分布受构造选择影响所以教材普遍把这个选项判定为错误。4. D选项的争议复盘为什么很多同学会纠结4.1 直觉推导的误区我当年做这道题也掉进过D的坑里。潜意识里觉得既然每次合并都取最小的两个那么最小两个叶子合并出来的结点权值一定很小而小数在后面的合并里会一直被优先选中所以整棵树最深的分支必然是最小两个叶子所在的分支。这个直觉本身不算错但它推出的是权值最小的两个叶子一定处于最大深度的那一层而不是它们是最深的两个结点。两者差别在哪里如果最深层只有这两个叶子两句话等价如果最深层还有其他叶子最深的两个这个表述就不精确了。出题人正是利用了这个细微差别把很多人心里差不多对的直觉做成了错误选项。4.2 为什么最深的两个不准确回到刚才{49,50,52,53,54,55}的例子最深层有三个实际上是四个49、50、52、53深度都是3。它们分属两个不同的分支如果题目把最深的两个理解为深度排名前二的两个结点那么在并列的情况下根本没有唯一的前二起码得说深度最大的四个结点才对。这种并列情况不是极端数据才能凑出来它的本质原因是只要有两对相邻的较小权值同时存在它们就会先各自合并再一起向上合并导致两对叶子拥有完全相同的深度。所以在复习时不要把D当成一个绝对错误的性质来背而是理解成深度和权值相关但不能简单下唯一性结论。4.3 应试立场与正确记忆方式站在考试立场上这道题标准答案就是D你不需要在考场上挑战它只需要知道最小两个一定互为兄弟是对的最小两个一定唯一最深是错的。更稳妥的记忆方式是权值越小的叶子深度不会小于权值更大的叶子——这是趋势可靠最深的两个结点这种绝对值表述在哈夫曼树语境下要警惕遇到直接按错误处理做题时用A、B、C的正确性来锁定D比单独判断D更快。5. 从这一题延伸哈夫曼树在408里的其他高频考法5.1 WPL与编码长度计算WPL是哈夫曼树最经典的计算题408特别喜欢换着方式考。一种考法是给一组权值让你求最小WPL另一种是给一棵已构造好的哈夫曼树让你算WPL还有一种是结合编码长度来考叶子的哈夫曼编码长度就等于它的深度所以所有字符编码长度的加权平均就等于WPL除以总权重如果是频率权重。计算时优先用我刚才说的合并累加法每轮合并都把新结点权值累加进去不容易出错。这个方法在做大题时也能省不少时间尤其是树形复杂、深度容易数错的时候累加轮次比数深度可靠得多。5.2 前缀码判定与字符编码哈夫曼编码是前缀码也就是说任何一个字符的编码都不是另一个字符编码的前缀。408可能会给你几组编码让你判断哪一组可能是哈夫曼编码这时候有两个思路一是看这些编码能否对应一棵二叉树把所有编码按0/1路径画出来看是否全部落在叶子位置二是看编码长度是否满足哈夫曼树的深度分布特征。更直接的做法是反推出权值如果把编码看作路径那么编码越长说明权值越小。所以你可以把编码按长度排序长度越长权值越小然后检查它是否符合哈夫曼合并过程。不过这个做法对数据量大的情况比较麻烦考场上通常用前缀码叶子全在底部判断就够。5.3 结点数计算与哈夫曼树不唯一n个叶子字符构造哈夫曼树总结点数是2n-1这个结论前面已经推过。408里还有一种考法是反过来给出一棵树的总结点数反推叶子数或者在选择题里混入度为1的结点可能存在这种错误说法。另外要注意哈夫曼树不唯一但WPL唯一。权值相同的结点选择顺序不同树的形状会不同编码也可能不同但最小带权路径长度只有一个确定值。这个点偶尔会出现在以下说法正确/错误的是的判断里记住树形不唯一、WPL唯一基本不会错。5.4 与其他数据结构的组合问题哈夫曼树在408里不是孤立的它经常和堆结合考。用最小堆实现哈夫曼构造是最常见的实现方式初始把n个权值建一个最小堆每次从堆顶取两个最小元素合并生成新结点插入堆中重复n-1次。整个过程的时间复杂度是O(nlogn)。选择题如果问用最小堆构造哈夫曼树的时间复杂度答案就是O(nlogn)这个结论直接记。此外还有把哈夫曼编码和字符频率统计结合的题型比如统计一段文本的字符频率后构造哈夫曼树再问编码方案或总编码长度。本质上还是WPL计算只不过把权值换成了频率。6. 易错点总结与复习建议6.1 高频易错自查清单整理几个我在答疑时经常看到同学踩的坑考前可以对着自查哈夫曼树不是二叉排序树它的中序遍历并没有排好序不要试图用中序去验证树是否正确WPL计算时容易把根结点的权值也算进去根权值是所有叶子权值之和对应所有字符的编码总长度之和不是计算WPL要的是每个叶子权值乘深度再求和根结点不参与编码时左右孩子分配0和1没有强制规定所以哈夫曼编码不是唯一的但任意一种方案只要符合左0右1或左1右0的规则编码长度不变哈夫曼树一定是最优二叉树是正确的但给定权值构造出的哈夫曼树唯一是错的。参考答案 WPL 2×4 3×4 4×3 7×2 11×1 57 哈夫曼编码的一种方案2为00003为00014为0017为0111为1。6.2 针对这类判断题的做题方法回到2010年第6题这类性质判断题我的建议是不要在四个选项里挨个凭感觉打勾而是先把哈夫曼树的核心结论在草稿纸上画一遍第一次合并的必然是两棵权值最小的树所以最小两个互为兄弟n个叶子对应n-1次合并对应n-1个度为2的结点没有度为1的结点合并越晚结点权值越大位置越接近根所以下面层的权值不会超过上面层深度最大层可以有多个叶子不能想当然地认为深度前二就是权值最小的两个。把这四条列出来之后再对照选项A、B、C都能直接对上剩下D自然就出来了。这个做题思路比死记四个性质通用得多换任何一套真题的性质判断题都适用。我个人的体会是刷408真题不要把每道题只当成选一个答案像2010年第6题这种四句话全是考点的题把每个选项当成判断题来分析一遍收获比做十道计算题还大。尤其是D选项如果你只是在错题本上写一个哈夫曼树的最小两个不一定最深没过几天还是会忘。只有亲手推一遍那个并列最深的例子才能真正理解一定两个字在数据结构选择题里有多危险。