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

对 $n$ 个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有 $115$ 个结点，则 $n$ 的值是（ ）。

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

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

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

1. 考纲定位：GESP六级“数据结构与算法”模块，考查哈夫曼树结点关系。命题人用“总节点数”卡住多数考生——他们只记“内部节点=叶节点−1"，却忘了把根节点也计入总数，导致算出57.5或57这类错误答案。

2. 解题思维：n个不同频率的符号，哈夫曼算法每步合并两棵树，共执行n−1次合并。因此内部节点数=n−1，总节点数=叶节点+内部节点=n+(n−1)=2n−1。已知2n−1=115，解得n=58。

3. 陷阱拆解：选项C(57)来自“总节点=内部节点+叶节点，内部节点=叶节点−1"的简化记忆，却把根节点漏掉；选项D(56)是误用“总节点=2n−2"(把根节点当成叶节点)；选项A(60)则是把公式倒过来用（n=总节点/2）。这些错误都源于对“二叉树中节点总数=2×叶节点−1"这一性质的机械套用，而非真正理解合并过程。

4. 反命题思维：若把条件改为“该哈夫曼树有115个内部节点"，则叶节点数=n=115+1=116，总节点=231。命题人常换问法考察同一关系，先问“内部节点数”再问“叶节点数”，本质都是2n−1。