🏷️ 知识点：Ds.05.05.01
在有 n 个叶结点的哈夫曼树中，非叶结点的总数是（ ）。
A. n−1 B. n C. 2n−1 D. 2n
[tag_link]
正确答案：A
推导
含 n 个叶结点的哈夫曼树是严格二叉树。设分支结点数为 n₂，由 n₀=n₂+1 得 n₂=n−1，故选 A。
易错点
不要把总结点数 2n−1 误当作非叶结点数；题目只问分支结点。
下列编码中，不是前缀编码的是（ ）。
A. {00, 01, 10, 11} B. {0, 1, 00, 11} C. {0, 10, 110, 111} D. {10, 110, 1110, 1111}
[tag_link]
正确答案：B
推导
前缀编码要求任一码字都不是另一码字的前缀。B 中 0 是 00 的前缀，1 也是 11 的前缀，因此 B 不能即时无歧义译码。
易错点
检查时要逐个短码与所有长码的开头比较；码长不同并不自动违反前缀条件。
设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对多少个字符编码？
A. 2 B. 3 C. 4 D. 5
[tag_link]
正确答案：C
推导
码字 1 占据根的 1 分支，码字 01 占据 01 叶位；剩余只能位于 00 子树。长度上限为 4 时，00 可扩展成 0000、0001、0010、0011，共 4 个码字，故选 C。
易错点
不能再使用以 1 或 01 开头的码字，也不能把内部前缀 0、00 同时当作码字。
一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到多少个不同的码字？
A. 107 B. 108 C. 214 D. 215
[tag_link]
正确答案：B
推导
哈夫曼树只有度 0 和度 2 的结点，若叶数为 n，则总结点数为 2n−1。由 215=2n−1 得 n=108，每个叶结点对应一个码字，故选 B。
易错点
内部结点不对应源符号码字；码字数等于叶结点数，不等于总结点数。
设某哈夫曼树有 5 个叶结点，则该哈夫曼树的高度最高可以是（ ）。
A. 3 B. 4 C. 5 D. 6
[tag_link]
正确答案：C
推导
根为第 1 层。5 个叶结点对应 4 个分支结点；令分支结点尽量形成一条链，每层另接一个叶结点，最深叶可到第 5 层，所以最高高度为 5，选 C。
易错点
题目按结点所在层数计高度；若改用边数计高度，数值会少 1，必须先看约定。
以下对于哈夫曼树的说法中，错误的是（ ）。
A. 用一组权值构造出的哈夫曼树可能不唯一，但带权路径长度唯一 B. 哈夫曼树具有最小的带权路径长度 C. 哈夫曼树中没有度为 1 的结点 D. 哈夫曼树中除了度为 1 的结点，还有度为 2 的结点和叶结点
[tag_link]
正确答案：D
推导
二叉哈夫曼树是严格二叉树，结点的度只能为 0 或 2，不存在度为 1 的结点，因此 D 声称存在度 1 结点是错误的。其余三项分别描述形态可不唯一、WPL 最小和严格二叉性质。
易错点
权值相同时树形可能不同，但最小 WPL 不变；不要把树形唯一与最优值唯一混为一谈。
若度为 m 的哈夫曼树中，叶结点数为 n，则非叶结点的个数为（ ）。
A. n−1 B. ⌊n/m⌋−1 C. (n−1)/(m−1) D. ⌈n/(m−1)⌉−1
[tag_link]
正确答案：C
推导
m 叉哈夫曼树的结点度只能为 0 或 m。设非叶结点数为 i，由边数 mi=n+i−1 得 i=(n−1)/(m−1)，故选 C。
易错点
该式要求叶数满足可构造条件；否则构造前应补权值 0 的虚叶，使 (n−1) 能被 (m−1) 整除。
设给定权集 W={5,7,2,3,6,8,9}，构造关于 W 的一棵哈夫曼树，并求其带权路径长度 WPL。
[tag_link]
参考答案
依次合并两个最小权值：2+3=5，5+5=10，6+7=13，8+9=17，10+13=23，17+23=40。因此 WPL=5+10+13+17+23+40=108。
推导过程
叶深复核：2、3 的深度为 4，原权值 5、6、7 的深度为 3，8、9 的深度为 2；故 WPL=(2+3)×4+(5+6+7)×3+(8+9)×2=108。左右子树可以互换，不影响 WPL。
复杂度与边界
最小堆构造时间 O(n log n)、空间 O(n)；单权值时 WPL=0。
易错点
每次都要把新权值放回集合；WPL 是各次合并权值之和，不是叶权值之和。
评分要点
- 写全六次合并
- 得出 WPL=108
- 能用叶深或合并和复核