GESP 六级 · GESP 202603 C++ 六级 第 19 题

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

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

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

【考点】哈夫曼编码｜完全二叉树定义｜贪心策略

GESP六级算法模块核心考点。命题人卡住学生"哈弗曼树形状唯一性"的盲区——默认相等频率必得对称树，却忘了合并顺序任意性。

解题思维链：①看到"频率相同"先联想贪心合并规则——每次取最小两节点；②关键观察：相等频率下合并顺序不固定，导致树形不唯一；③反证：若为完全二叉树，则末层必左满右缺，但3个等频字符合并后，根左右子树高度差1，末层只有1个叶子在左，右子为内节点，违反完全二叉树定义。结论：频率相同仅保证树高为⌈log₂n⌉，不保证结构唯一。

陷阱拆解：A选项"正确"源于混淆"平衡树"与"完全二叉树"——命题人利用学生只记结论不溯本源的弱点，将"树高最矮"偷换为"结构唯一"。最阴险细节是"一定"二字，绝对化表述暴露了命题人对Huffman算法非确定性本质的考察。若只背"哈夫曼树是二叉树"，就会忽略合并顺序对末层填充的影响。例如n=3时，根左右子树高度差1，末层只有1个叶子在左，右子为内节点，违反完全二叉树定义。

反命题思维：若改为"频率成等比数列"，Huffman树高度仍为⌈log₂n⌉，但结构更趋向左偏；若限定"合并顺序始终取最左侧两节点"，则等频下必得完全二叉树——命题人常在此处设陷阱。刷到含"一定"的哈弗曼题，先问自己"合并顺序被固定了吗？"。当n=2^k时，哈弗曼树可构造为完全二叉树，但非必然。