GESP 六级 · GESP 202506 C++ 六级 第 17 题

给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。

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

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

【考点】哈夫曼树构造｜编码唯一性判定｜贪心算法

1. 🎯 考纲定位 本题考查 GESP 六级《算法基础》中哈夫曼树专题的核心理解。命题人专门拿这道题卡住 80% 以上的考生——他们死记"哈夫曼编码是最优前缀码"，却混淆了"编码最优"和"树结构唯一"这两个完全不同的概念。

2. 🧠 解题思维 构造哈夫曼树时，每一步都要从当前所有子树中选取两个频率最小的合并。关键观察：当存在多个频率相同的子树时，选取哪两个合并会产生不同结果。例如频率集合{1,1,2,3,5}，两个1可以分别与2或3合并，形成不同形状。但无论怎么合并，最终所有叶子到根路径长度之和（即带权路径长度）都等于同一最小值。因此树的结构不唯一，但编码的平均长度是唯一的。

3. 🪤 陷阱拆解 选项 A 的"正确"是典型偷换概念陷阱——把"最优"偷换成"唯一"。命题人利用考生对"唯一"的绝对化理解：以为最优解必然对应唯一结构。事实是，哈夫曼编码唯一是指每个字符对应的码字集合唯一（不考虑码字排列顺序），而不是指树形结构唯一。题目特意用"构造出的哈夫曼树"这个表述，就是锁定结构而非编码。

4. 🔄 反命题思维 如果题目改成"给定字符频率，哈夫曼编码的平均长度是唯一的"，那答案就是正确。刷到类似题先问自己：它问的是树结构还是编码结果？这两个在哈夫曼专题里是不同考点。