题目

对任意给定的含 n (n > 2) 个字符的有限集 S, 用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。下列叙述中，正确的是 ( )。

错因

A

只在 为 2 的整数次幂时才"碰巧"相等。哈夫曼树是严格二叉树（每个内部结点恰有 2 个孩子）， 个叶子对应 个结点。而定长编码树是深度为 的满二叉树（再把多余的叶子位置闲置），结点数是 。例如 ：T1 共 5 个结点，T2 共 7 个结点，并不相等。

B

把"哈夫曼树倾向于让高频字符靠近根、低频字符深"的特点错误地推广为"T1 一定比 T2 高"。当所有字符频次相等时，哈夫曼算法每一步合并出的子树高度齐平，最终 T1 退化成一棵满二叉树，与 T2 高度相同；当频次差异不极端时，两者也可能等高。所以"T1 > T2"不是普遍成立的结论。

C

误以为"频次不同 ⇒ 编码长度不同 ⇒ 层不同"。反例：、频次为 。哈夫曼合并顺序为 、、，结果频次为 1 和 2 的两个字符都在第 3 层（深度相同），但它们频次并不相同。所以"频次不同则层不同"不成立。

总解析

思路：定长编码 vs 哈夫曼编码的核心区别——

• 定长编码 T2：所有字符用同样多的二进制位表示，因此每个字符必然位于二叉树同一层（叶层），与字符出现频次无关。
• 变长哈夫曼编码 T1：高频字符靠近根（短码），低频字符远离根（长码），不同字符可能在不同层，但两个频次不同的字符也可能恰好在同一层（合并过程的副产物）。

逐项核对：

• A：结点数 T1 = （严格二叉树），T2 与 是否为 2 的幂相关，一般不等。✗
• B：频次相等或接近时 T1 也可能与 T2 等高，不必然更高。✗
• C：见上反例，T1 中频次不同的字符可能同层。✗
• D：T2 是定长编码，所有字符都在同一层（叶层），无论频次如何。✓

最终答案是 D。