题目

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度(WPL)是( )。

错因

A

误把根的权值当 WPL。哈夫曼合并到最后剩一个根结点，权值是 89（= 所有叶子权值之和），这是哈夫曼树的"总和"而不是 WPL。WPL 要按"叶子权 × 路径长度"求和，不是简单相加叶子权。

C

贪心选择没回到候选集挑最小。每次合并后必须把新结点丢回候选集，再从所有候选里重新选两个最小。常见错法：把上一步合并结果直接和"还没合并过的下一个数"再合并，得到错误顺序。例如：10+12=22，然后误把 22+16=38（应回到 16, 21, 22, 30 中重选 16 和 21），后续 38+21=59、59+30=89，非叶结点权之和 22+38+59+89=208。

D

把所有结点（叶子+非叶子）的权值都加上。计算时不分清"WPL = 非叶子结点权值之和"这一公式；把 5 个叶子权值（10+12+16+21+30=89）和 4 个非叶子权值（22+37+52+89=200）一起加：89+200=289。叶子的权已经在父结点合并时累计过，不能再单独加。

总解析

思路：哈夫曼树是给定叶子权值后 WPL 最小的二叉树。构造法是反复挑选当前权值最小的两棵子树合并，直到合成一棵。WPL 有两种等价算法，第二种在选择题里更省时。

算法 1（定义法）：WPL = ∑(叶子权 × 叶子到根的路径长度)。

算法 2（合并法）：WPL = 所有非叶子结点的权值之和。原因：每个叶子的权在它所在的每一层向上合并时都被累加了一次，恰好等于路径长度倍。

构造哈夫曼树（贪心合并）：

步	当前候选集（升序）	选中合并	新结点权	操作后候选集
1		10 + 12	22
2		16 + 21	37
3		22 + 30	52
4		37 + 52	89

关键操作：每步合并后，新结点要重新放回候选集和其它原始权一起再排序，下一步从全集里挑最小两个。第 2 步要选的不是"上一步结果 22 + 下一个 16"，而是"当前候选 {16, 21, 22, 30} 里最小的两个" → 16 和 21。

用算法 2 求 WPL：

用算法 1 验证（哈夫曼树的层结构：30 在第 1 层下、22 在第 2 层下、{10, 12} 在第 3 层、{16, 21} 在第 2 层下、52 是 22 与 30 合并）：

哈夫曼树形状（基于上面的合并顺序，最后一次合并 52 = 22 + 30 与 37 = 16 + 21 在同一层）：

各叶子的深度：

• 16, 21：深度 2
• 10, 12：深度 3
• 30：深度 2

最终答案是 B（200）。

小结：选择题里优先用"算法 2 = 非叶子权之和"省去画树和数深度。但如果题目要求画哈夫曼编码或问某一编码的长度，还是要还原树结构。