企业官网建设流程全解析

做408真题做到数据结构部分，2010年第6题是一道绕不开的哈夫曼树判断题——四个选项全是性质描述，没有一个需要你现场构建整棵树，但当年不少人在D选项上翻了车。题目大意是：对n（n≥2）个权值均不相同的字符构造成哈夫曼树，判断下面四个叙述中哪一个是错误的。表面看是考性质记忆，实际上考的是你对哈夫曼树构造过程的理解深度：为什么最小两个结点互为兄弟？为什么树中没有度为1的结点？权值最小的两个结点是不是一定最深？这些如果只靠背结论，D选项就很容易选错。

这道题适合两类人反复琢磨：一类是正在刷408历年真题的考研党，另一类是学数据结构时对哈夫曼树只停留在"画树算WPL"阶段的同学。把这一题吃透，等价于把哈夫曼树这个考点最核心的几个性质全部过了一遍，后面再做编码、前缀码、WPL计算相关的题都会顺很多。

1. 先还原题目：2010年第6题是一道性质判断题

1.1 题目原文（常见版本）与考点定位

2010年408统考数据结构部分的第6题，题干和选项在许多复习资料里都有收录，常见版本如下：

对n（n≥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、5，3仍然是最小的，所以下一步还要拿这个新结点和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，右孩子16；16的左孩子7，右孩子9；9的左孩子4，右孩子5；5的左孩子2，右孩子3。

看这个结构，2和3在最底层，深度为3（从根往下数边数，根深度为0），4的深度也是3？不对，仔细看：4和5是9的孩子，9是16的孩子，16是根27的孩子，所以4的深度是3？根27深度0，16深度1，9深度2，4深度3，5深度3，2和3深度4。刚才说的结构里5下面还有2和3，所以5是内部结点。重新写清楚：9的左孩子4，右孩子5；5的左孩子2，右孩子3。那么2、3深度是4，4深度是3，5深度是2，7深度是2，11深度是1。

WPL计算：WPL=2×4+3×4+4×3+7×2+11×1=8+12+12+14+11=57。

这里分享一个我比较推荐的手算技巧：不用每次都先画完整树再数深度，直接按合并顺序累加"本次新结点的权值"，所有合并轮次的新结点权值加起来就等于WPL。以上面例子为例：

累加结果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}。第一步49+50=99，第二步52+53=105，第三步54+55=109。此时森林里是99、105、109，第四步99+105=204，第五步109+204=313。最终树形是：根313，左孩子109，右孩子204；204的左孩子99，右孩子105；99下面是49和50，105下面是52和53，109下面是54和55。算深度：49、50深度是3，52、53深度也是3，54、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为0000，3为0001，4为001，7为01，11为1。

6.2 针对这类判断题的做题方法

回到2010年第6题这类性质判断题，我的建议是不要在四个选项里挨个"凭感觉"打勾，而是先把哈夫曼树的核心结论在草稿纸上画一遍：

• 第一次合并的必然是两棵权值最小的树，所以最小两个互为兄弟；
• n个叶子对应n-1次合并，对应n-1个度为2的结点，没有度为1的结点；
• 合并越晚，结点权值越大，位置越接近根，所以下面层的权值不会超过上面层；
• 深度最大层可以有多个叶子，不能想当然地认为深度前二就是权值最小的两个。

把这四条列出来之后再对照选项，A、B、C都能直接对上，剩下D自然就出来了。这个做题思路比死记四个性质通用得多，换任何一套真题的性质判断题都适用。

我个人的体会是：刷408真题不要把每道题只当成"选一个答案"，像2010年第6题这种四句话全是考点的题，把每个选项当成判断题来分析一遍，收获比做十道计算题还大。尤其是D选项，如果你只是在错题本上写一个"哈夫曼树的最小两个不一定最深"，没过几天还是会忘。只有亲手推一遍那个并列最深的例子，才能真正理解"一定"两个字在数据结构选择题里有多危险。