题目

对 n (n≥ 2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。

错因

B

哈夫曼算法每次选两个最小结点合并，生成的新内部结点必有两个孩子（度为 2），叶结点度为 0，整棵树确实不存在度为 1 的结点。B 是正确性质，误认为它是错误项的人可能把"合并"步骤和"插入"步骤混淆了。

C

哈夫曼算法第一步就是从所有结点里选出权值最小的两个，将它们合并为兄弟，这是算法的直接定义。C 是正确性质，误选 C 的人可能不熟悉算法流程。

D

哈夫曼树任意内部结点的权值 = 其两个子结点权值之和，因此内部结点权值 ≥ 任一子结点权值。这一性质沿层级向下递推对整棵树都成立。D 是正确性质。

总解析

哈夫曼树不一定是完全二叉树，A 是错误叙述。

构造过程：每次选权值最小的两个结点合并，合并顺序完全由权值大小决定，与位置无关，不保证每层从左到右填满。

反例：权值集合 {1, 2, 4, 8}。

• 合并 1+2=3，森林：
• 合并 3+4=7，森林：
• 合并 7+8=15，得到根

最终树形：

        15
       /  \
      7    8
     / \
    3   4
   / \
  1   2

该树最后一层只有 1 和 2 两个叶子，位于最左侧，但 8 是右子树的叶子且只有一个，树形左右不对称，不是完全二叉树。

B、C、D 均是哈夫曼树的正确性质。

最终答案是 A。