题目

已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为 6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是( )。

错因

B

直接踩了"前缀码"红线。注意 a 的编码是 00，d 的编码是 000——00 是 000 的前缀。一旦解码读到 000…，无法判断是 00 接下个字符的开头 0，还是整段 000 是 d。哈夫曼编码必须是前缀码（任何编码都不是另一个编码的前缀），B 一开始就不合法，根本进入不了"是否最优"的讨论。

C

也是前缀冲突。a=10 而 b=1011，10 是 1011 的前缀，解码 1011 时分不清是 a 后面跟 11 还是整段 b。前缀码这一关都过不去，无论 WPL 多小都不算哈夫曼编码。

D

D 的编码两两之间不互为前缀（可以逐对验证：0011/0010 前 3 位相同但第 4 位不同；000/0010/0011 都不互为前缀；01、10、11 长度都是 2 互不相等），所以 D 是合法的前缀码。但合法前缀码不等于哈夫曼编码——后者还要求 WPL（带权路径长度）最小。逐位算 D 的 WPL：

字符	频次	D 的编码	长度	贡献
a	6	0011	4	24
b	3	10	2	6
c	8	11	2	16
d	2	0010	4	8
e	10	01	2	20
f	4	000	3	12
WPL				86

而真正的哈夫曼 WPL = 80（推导见下），D 多出 6，不是最优解，也就不是哈夫曼编码。多数同学会因为"看上去也是变长前缀码"而被这个选项坑到。

总解析

判断一组编码"可不可能是哈夫曼编码"，按以下两道关卡过：

1. 是不是前缀码？任何编码不能是另一个编码的前缀，否则解码歧义，直接淘汰；
2. WPL 是不是最优？按字符频率合并，得到最小 WPL；候选编码的 WPL 与之相等才算合格。

第一步：用合并算法求最小 WPL

把权值排序：。

每次取两个最小的合并，新权值放回继续：

步骤	当前队列（升序）	取出	新结点权值
1	2, 3, 4, 6, 8, 10	2 + 3	5
2	4, 5, 6, 8, 10	4 + 5	9
3	6, 8, 9, 10	6 + 8	14
4	9, 10, 14	9 + 10	19
5	14, 19	14 + 19	33（根）

最小 WPL = 所有非叶结点权值之和：。

第二步：候选选项逐个过两道关

• A 编码为 a=00, b=1011, c=01, d=1010, e=11, f=100
  • 前缀码检验：长度 2 的 00, 01, 11 互不相同；100 与长度 4 的 1010, 1011 在第 3 位就分叉（100 的第 3 位是 0，而 1010, 1011 的第 3 位是 1），互不为前缀；1010 和 1011 前 3 位相同但第 4 位不同。✓ 合法前缀码。
  • WPL： ✓
  • 通过两关，是哈夫曼编码的一种合法形态（哈夫曼编码因为左右子树指派 0/1 的方式以及合并时"哪个新结点先取"的次序差异，并不唯一，但任意一种合法哈夫曼编码的 WPL 必定等于 80）。
• B：00 是 000 的前缀 → 不是前缀码，淘汰。
• C：10 是 1011 的前缀 → 不是前缀码，淘汰。
• D：是前缀码，但 WPL = 86 > 80 → 不是最优，淘汰。

最终答案是 A。