GESP 七级 · GESP202609 C++ 七级 第 3 题

有 4 个字符，出现次数分别为 1、2、3、4。构造哈夫曼树后，出现次数为 1 的字符的哈夫曼编码长度为（ ）。

哈夫曼编码的核心是贪心合并：每次选两个最小权值节点合并为新节点，直到只剩根节点。编码长度等于叶子节点到根的路径长度（边数）。本题只需按规则构造哈夫曼树，再数出频率为 1 的字符所在叶子节点的深度即可。

易错点一：误以为所有字符编码长度相同，直接选 2 或 3。易错点二：把"编码长度"理解成"该字符在树中占用的总位数"，而非"从根到该字符的路径长度"。易错点三：合并顺序出错，比如先合并 3 和 4 得到 7，导致树形变化。易错点四：混淆节点权值与编码长度，权值 1 的字符编码长度未必是 1。

1. 考纲定位

本题考查《GESP 考试大纲》七级"数据结构与算法"模块中的哈夫曼编码知识点。命题人放这道题，是因为七级考生普遍对"贪心构造哈夫曼树"的流程掌握不牢，容易在合并顺序和编码长度计算上出错，这道题就是专门卡住这个弱点的。

2. 解题思维

哈夫曼编码的构造规则是固定的：每次从当前所有节点中选出两个权值最小的节点，合并成一个新节点，新节点的权值等于两个子节点权值之和。重复这个过程，直到只剩一个根节点。

编码长度等于叶子节点到根节点的路径长度（边数）。

数值推演：

初始节点：1, 2, 3, 4

• 第 1 次合并：选最小的 1 和 2，合并得新节点 3。剩余：3, 3, 4
• 第 2 次合并：选最小的 3 和 3，合并得新节点 6。剩余：4, 6
• 第 3 次合并：选最小的 4 和 6，合并得根节点 10。完成。

画出树结构：

 10
 / \
 4 6
 / \
 3 3
 / \
 1 2

频率为 1 的字符在树中位于最左下方的叶子节点。从根到该节点的路径：10→6→3→1，经过3 条边，所以编码长度为 3。

这一类题的通法： 1. 按权值从小到大排序，每次合并两个最小节点 2. 记录合并后的新节点权值，放回集合 3. 重复直到只剩一个节点 4. 编码长度 = 叶子节点深度（边数）