GESP 七级 · GESP 202606 C++ 七级 第 22 题

哈夫曼树中不存在度为 $1$ 的结点。

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

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

【考点】哈夫曼树构造原理｜满二叉树结构｜树结点度

🎯 考纲定位：本题考查 GESP 七级《数据结构》中哈夫曼树的性质，命题人刻意用"度为 1 的结点"这一绝对化表述卡住只会背结论的考生——他们知道哈夫曼树是满二叉树，却说不清"满二叉树"与"度"的数学定义。

🧠 解题思维：哈夫曼树的构建规则是：每次选取当前权值最小的两个结点合并为新父结点。新父结点必然有两个子结点，因此内部结点度恒为 2。叶子结点由原始字符生成，度为 0。由构造过程可知，哈夫曼树中每个内部结点均由两个子结点产生，不存在仅含一个子结点的内部结点，故全树无度为 1 的结点。本质是"哈夫曼树必为满二叉树"的构造性证明。

🪤 陷阱拆解：命题人利用"度"的定义偷换概念——许多考生混淆"二叉树"与"满二叉树"，以为普通二叉树中可存在度为 1 的结点，直接误选 B。更阴险的是"不存在"这一绝对化表述，若考生只记"哈夫曼树是二叉树"而不理解"满二叉树"的构造约束，就会在边界情况（如根结点）上动摇。即便树只有一个结点，根结点度为 0，依然满足"无度为 1 的结点"。

🔄 反命题思维：若将题干改为"哈夫曼树中所有内部结点的度都是 2"，答案不变；若换成"一般二叉树中不存在度为 1 的结点"，答案翻转为 B。刷到此类树结构判断题，先问自己：题目考的是"任意二叉树"还是"哈夫曼树"？构造规则是否强制了满二叉？