GESP 六级 · GESP202609 C++ 六级 第 22 题

哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更 长。

哈夫曼编码的核心是构建一棵二叉树，每次合并两个频率最小的节点，频率高的字符自然落在树的浅层，频率低的字符落在树的深层。编码长度等于节点深度，因此高频字符的编码长度一定不超过低频字符。

学生容易把"一定不会"误读为"可能不"，或者混淆哈夫曼编码与等长编码（如ASCII）的区别。还有人会纠结"频率相同怎么办"，其实频率相同时深度相同，结论依然成立。

1. 考纲定位

本题考查贪心算法在哈夫曼编码中的具体应用，属于GESP六级《数据结构与算法》模块。命题人放这道题，就是要卡住那些只背定义、不懂构造过程的学生——他们知道哈夫曼编码"压缩率高"，但说不清为什么高频字符的编码一定短。

2. 解题思维

看到题先想哈夫曼树的构造规则：每次从节点集合中取出两个频率最小的节点合并，新节点的频率是两者之和。这个贪心策略保证了最终生成的二叉树中，频率越高的节点离根越近。

关键观察：编码长度等于节点深度。根节点深度为0，每往下一层深度加1。因为高频节点在浅层，低频节点在深层，所以高频字符的编码长度一定≤低频字符的编码长度。

数值推演：假设字符A频率0.5、B频率0.25、C频率0.25。第一步合并B和C（频率最小），得到新节点BC频率0.5；第二步合并A和BC，得到根节点。A深度1，B和C深度2。确实高频字符编码更短。