GESP 七级 · GESP202609 C++ 七级 第 18 题

在哈夫曼树中，出现次数更多的叶子结点，其深度总是更小。

哈夫曼树是贪心构造的：每次从优先队列里挑两个频率最小的叶子合并，新节点频率等于两者之和再放回队列。频率越大的叶子，越早被合并，离根越近，深度就越小。

错误选项常把"深度"偷换成"高度"或"层数"，或者用平衡二叉树的性质来干扰。本题最阴险的细节是"总是"二字——如果两个频率相同，它们深度必然相等，但命题说的是"出现次数更多"，即严格大于，所以深度严格更小，逻辑无懈可击。

1. 考纲定位

本题考查贪心算法与哈夫曼树性质，对应《GESP 考试大纲》七级"数据结构与算法"模块。命题人卡住的是对贪心策略与树结构关系的理解，很多考生只背"哈夫曼树"名词，却说不清为什么频率高的叶子一定更浅。

2. 解题思维

哈夫曼树的构造过程是典型的贪心：维护一个最小堆，每次弹出两个频率最小的节点合并，新节点频率为两者之和，再压回堆中。这个过程的本质是——频率大的节点被合并得晚，因此离根更近。

用一组具体数字推演：假设有 4 个叶子，频率分别为 1、2、3、4。

• 第 1 次合并：1+2=3，堆变为{3,3,4}
• 第 2 次合并：3+3=6，堆变为{4,6}
• 第 3 次合并：4+6=10，得到根

看深度：频率 4 的叶子在第 3 次才参与合并，深度为 1；频率 1 的叶子在第 1 次就参与合并，深度为 3。频率大的深度小，结论成立。