GESP 六级 · GESP 202606 C++ 六级 第 21 题

哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。

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

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

【考点】哈夫曼树构建｜贪心策略｜编码唯一性

🎯 考纲定位：GESP 六级 数据压缩模块，命题人专卡"哈夫曼编码唯一性"这个高频易错点——多数考生背了"哈夫曼编码是最优前缀码"就以为它天然唯一，完全没意识到合并顺序带来的歧义空间。

🧠 解题思维：哈夫曼算法本质是贪心合并，每次挑频率最小的两个节点合并成父节点。当存在多个相同频率的节点时，"选哪两个先合并"这一步就有自由度——比如频率集合{2,2,2,3}，第一次合并可以选任意两个 2，合并后得到{4,2,3}，再合并 2 和 3 得到{7}，最终树形可能不同。树形不同，从根到叶的路径就不同，编码自然不同。

🪤 陷阱拆解：A 选项"一定唯一"是绝对化表述，命题人用"只要字符频率相同"这个条件诱导你忽略合并顺序的歧义。其实哈夫曼树唯一性的充分必要条件是"所有节点频率互不相同"。此外还有两个隐藏坑：1) 左右子树交换不影响前缀码但会影响编码字典序；2) 不同实现可能给相同频率的节点打不同优先级标签。

🔄 反命题思维：把题改成"所有字符频率互不相同"，结论就反转为正确。刷到此类题先问自己"频率分布里有没有相等值"，这是判断哈夫曼树唯一性的核心判别条件。