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

哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

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

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

【考点】哈夫曼编码｜二叉树结构｜前缀编码

1.考纲定位：六级考查树形数据结构的编码应用，重点在"前缀编码"与"叶子结点"定义。命题人卡住的是学生把"前缀编码"误认为"前缀冲突"，却忽略树形几何约束。

2.解题思维：哈夫曼树的本质是二叉树，叶子结点（对应字符）不可能有子结点。若叶子结点成为另一结点的祖先，则它必须包含子结点，这与"叶子结点"定义矛盾。因此所有字符的编码都互不为前缀，解码时从前缀匹配就能唯一还原。

3.陷阱拆解：陷阱在于把"前缀编码"概念偷换成"前缀冲突"。命题人利用学生死记硬背"哈夫曼编码无前缀"的结论，却忽略其几何本质：二叉树中叶子结点不可能有子结点。若误以为"叶子结点"能"包含"其他字符，就会在选项里掉进"前缀编码"的语义陷阱。

4.反命题思维：命题人想考"叶子结点不可能有子结点"这个几何事实，而非"哈夫曼编码无前缀"这个编码性质。若把树换成三叉树或完全二叉树，答案不变。

一句话提醒：刷到类似题，先确认"叶子结点"定义，再判断是否涉及编码性质。