GESP 七级 · GESP 202603 C++ 七级 第 13 题

有 $6$ 个字符，它们出现的次数分别为：$\{2, 3, 3, 4, 6, 8\}$，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL（每个字符的出现次数 $\times$ 它的编码长度，再把每个字符结果加起来）的值为（ ）。

哈夫曼编码：每次合并权值最小的两个节点，构建最优二叉树，使带权路径长度（WPL）最小。用于数据压缩。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】哈夫曼编码

1. 考纲定位 GESP 七级「数据结构与算法」模块中，哈夫曼编码是核心考点之一。命题人特意选这道题，就是想卡住部分考生对「贪心策略」的理解——很多人知道哈夫曼编码的原理，但做题时容易在合并步骤出错，导致 WPL 算错。考试要求能构造哈夫曼树并计算 WPL，这是数据压缩的基础技能，也是后续树形结构题的前提。

2. 解题思维 看到频数集合 {2,3,3,4,6,8}，第一步必须按从小到大排序。贪心合并规则是：每次取当前最小的两个频数相加生成新节点，放回集合继续合并。具体步骤：

• 合并 2+3=5，集合变为 {3,4,5,6,8}
• 合并 3+4=7，集合变为 {5,6,7,8}
• 合并 5+6=11，集合变为 {7,8,11}
• 合并 7+8=15，集合变为 {11,15}
• 合并 11+15=26

WPL 等于所有内部节点权值之和：5+7+11+15+26=64。注意：6 个叶子对应 5 个内部节点，每个内部节点权值是其子节点之和，WPL 正是这些内部节点权值累加。

3. 陷阱拆解 选项 A(58) 和 C(62) 是怎么来的？常见错误有：

• 忘记把新生成的节点也参与后续合并，导致内部节点数少算，WPL 偏小；
• 合并时没有始终选最小的两个，比如先合并 6+8=14，WPL 会变大；
• 误把叶子权值也加进 WPL 计算（例如 64+26=90，不在选项中，但说明概念混淆）。

题目中「最小加权路径长度」的定义是「每个字符出现次数 × 编码长度之和」，等价于内部节点权值和，这个等价关系是命题人埋下的概念陷阱——只背结论不推导的人容易选错。

4. 反命题思维 如果题目改成「求哈夫曼树中编码最长的字符」，答案就不是 WPL 了，而是看树的高度，此时需要重新分析树的结构。再比如，若频数集合改为 {1,1,1,1,1,1}，合并过程不同，WPL 会变成 5，而不是 64。做这类题时，先问自己：命题人想考我哪一步的贪心选择？WPL 计算是否遗漏了某个内部节点？这样才能避免掉进陷阱。