GESP 六级 · GESP 202503 C++ 六级 第 16 题

哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。

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

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

【考点】哈夫曼树构建｜贪心策略｜带权路径长度

🎯 考纲定位 GESP 六级《数据结构》模块，明确考查哈夫曼树构建原理。命题人卡住的是考生对"贪心策略"与"最优性"关系的认知——很多人背了"合并最小两个"就认为过程正确，却忽略了为何这样能得到全局最优，这是六级区分度所在。

🧠 解题思维 正确。哈夫曼树是带权路径长度最小的二叉树，其构造过程严格遵循贪心策略：每次从所有未合并节点中选取两个权值最小的合并为新节点，重复直至只剩根节点。该过程不仅保证了树的形态（满二叉树），更通过局部最优选择累积成全局最优解，即 WPL 最小。这是哈夫曼算法的核心证明结论，也是六级重点。

🪤 陷阱拆解 错误选项 B 的陷阱在于混淆"构造过程"与"树结构"。命题人利用考生对"合并最小两个"这一操作的手感记忆，诱导认为只要按此步骤操作就能得到哈夫曼树，却忽略了该操作是*唯一*保证 WPL 最小的构造方式。若考生只背结论而不理解贪心证明的直观性，就会误判此题为"过程描述不完整"或"定义不严谨"，从而选错。

🔄 反命题思维 若将题干改为"哈夫曼树一定是平衡二叉树"，答案立即变为 B——哈夫曼树只保证 WPL 最小，不保证高度平衡，这是六级常考的"概念辨析"。刷到类似题，先自问：命题人想考我"构造过程"还是"结构性质"？前者是算法，后者是树论。