🏷️ 知识点：哈夫曼树

下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。

哈夫曼树

A. 24, 10, 5 和 24, 10, 7 B. 24, 10, 5 和 24, 12, 7 C. 24, 10, 10 和 24, 14, 11 D. 24, 10, 5 和 24, 14, 6

[tag_link] 正确答案：D在 哈夫曼树 中，左右孩子权值之和为父结点权值。仅以分析选项 A 为例：若两个 10 分别属于两棵不同的子树，根的权值不等于其孩子的权值和，不符；若两个 10 属于同棵子树，其权值不等千其两个孩子（叶结点）的权值和，不符。B、C 选项的排除方法一样。

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

哈夫曼树

A. 56 B. 57 C. 58 D. 60

[tag_link]

正确答案：C

哈夫曼树 是一颗带权路径长度最短二叉树，有性质：n 个叶子结点的哈夫曼树，共 2n-1 个结点 2n-1 = 115 解得 n = 58，选 C。

已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。

树的概念 带权路径长度

A.27

B.46

C.54

D.56

[tag_link] 正确答案：B将 哈夫曼树 的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为 0 的虚叶结点，对于严格的三叉树(n0−1)%(3−1)=u=1\=0，需要添加m−u−1=3−1−1个叶结点，说明 7 个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为 0 的叶结点应离树根最远构造最小带权生成树的过程如下：最小的带权路径长度为(2+3)×3+(4+5)×2+(6+7)×1=46。

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼树的加权平均长度为（ ）

哈夫曼树

A. 2.4 B. 2.5 C. 2.67 D. 2.75

[tag_link]

正确答案：B

计算字符集 S 构造的 哈夫曼编码 的 加权路径长度，我们需要使用字符的频次来确定每个字符的编码长度，并计算加权平均值。给定字符集 S 中各字符出现的频次为 3，4，5，6，8，10，我们可以按照哈夫曼编码算法构造哈夫曼树。构建的哈夫曼树如图所示。加权平均长度 =（编码长度 1 × 频次 1 + 编码长度 2 × 频次 2 + … + 编码长度 n × 频次 n）/（频次 1 + 频次 2 + … + 频次 n），在本题中，加权平均长度=((3+4+5+6)×3 + (8+10)×2)/(3+4+5+6+8+10)=2.5。本题答案选 B。

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

哈夫曼树

A. 00, 1011, 01, 1010, 11, 100 B. 00, 100, 110, 000, 0010, 01 C. 10, 1011, 11, 0011, 00, 010 D. 0011, 10, 11, 0010, 01, 000

[tag_link]

正确答案：A

构造一棵符合题意的哈夫曼树，如下图所示。

由此可知，左子树为 0, 右子树为 1, 故答案为 A。这题也可以 使用排除法，因为哈夫曼编码是前缀编码，所以任意编码都不能是另一个编码的前缀，根据这一点可以排除掉 B、C 选项。D 选项也是错误的，因为字符 e 的出现次数为 10 很高，它不能哈夫曼编码长度最短，这不合理。

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是（ ）。

哈夫曼树

A. 89 B. 200 C. 208 D. 289

[tag_link]

正确答案：B

根据 Huffman 构建过程 来构建得到如下二叉树：

         89
      /      \
     52      37
   /   \    /  \
  22   30  16  21
 /  \
10  12

带权路径长度 为：(10+12)×3+(30+16+21)×2=200

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

A. T1 与 T2 的结点数相同

B.T1 的高度大千 T2 的高度

C. 出现频次不同的字符在 T1 中处于不同的层

D. 出现频次不同的字符在 T2 中处于相同的层

[tag_link]

正确答案：D

可以画一个简单的特例来证明。图 1 是满足条件的二叉树 T1，图 2 是满足条件的二叉树 T2，结点中有值表示这个结点是编码字符。T1 和 T2 的结点数不同，A 错误。T1 的高度等于 T2 的高度，B 错误。出现频次不同的字符在 T1 中也可能处于相同的层，C 错误。对于定长编码码集，所有字符一定都在 T2 中处于相同的层，而且都是叶子结点。

设字符集 S 包含 7 个字符，各字符出现的频次分别是 2, 3, 4, 6, 8, 10, 11。为 S 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符个数是（ ）。

哈夫曼树

A. 2 B. 3 C. 4 D. 5

[tag_link]

正确答案：D

按照 哈夫曼树 构造：频次为 2, 3, 4, 6, 8, 10, 11

1. 合并 2 + 3 = 5
2. 合并 4 + 5 = 9
3. 合并 6 + 8 = 14
4. 合并 9 + 10 = 19
5. 合并 11 + 14 = 25
6. 合并 19 + 25 = 44 （根）可以得到以下二叉树：

        44
      /    \
    19      25
   /  \    /  \
  9    10 11  14
 / \          / \
4   5        6   8
   / \
  2   3

编码长度不小于 3 的字符：2, 3, 4, 6, 8。一共有 5 个字符编码长度不小于 3，[tag_link]正确答案为 D。

在下列二叉树中，（ ）的所有非叶结点的度均为 2。 Ⅰ. 完全二叉树 Ⅱ. 满二叉树 Ⅲ. 平衡二叉树 Ⅳ. 哈夫曼树 Ⅴ. 二叉排序树

A. Ⅱ和Ⅳ B. Ⅰ和Ⅲ C. Ⅱ、Ⅳ和Ⅴ D. Ⅱ、Ⅲ和Ⅳ

树的概念 哈夫曼树

[tag_link]

正确答案：A

首先，理解题意：所有非叶结点的度均为 2，意味着二叉树中每个内部节点都必须有两个子节点。

接下来逐一分析所列二叉树类型：

完全二叉树的定义是除最后一层外，其他层节点数达到最大值，且最后一层节点尽量靠左排列。 > 在这种情况下，非叶结点可能只有一个子节点（例如，当树节点数较少时），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

满二叉树则严格要求每个节点要么是叶子节点（度为 0），要么有两个子节点（度为 2）。 > 因此，满二叉树的所有非叶结点度均为 2，符合条件。 >

平衡二叉树（如 AVL 树）主要关注左右子树高度平衡，不限制节点的度数。 > 在平衡二叉树中，非叶结点可能只有左子节点或右子节点，即度可以为 1，所以不满足要求。 >

哈夫曼树在构建过程中，每次合并两个节点形成新的内部节点，因此每个内部节点都有两个子节点。 > 哈夫曼树的所有非叶结点度均为 2，符合条件。 >

二叉排序树中，节点度数取决于插入顺序和树的结构，非叶结点常常可能只有一个子节点（例如，在偏斜树中），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

综上，只有满二叉树和哈夫曼树满足所有非叶结点的度均为 2，对应选项中的Ⅱ和Ⅳ，故正确答案为 A。 >

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

A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点 C. 树中两个权值最小的结点一定是兄弟结点 D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

[tag_link]

正确答案：A

哈夫曼树 为带权路径长度最小的二叉树，不一定是完全二叉树。

哈夫曼树中没有度为 1 的结点，B 正确；

构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C 正确；

哈夫曼树中任一非叶结点 P 的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点 P 的左、右子树根结点处于同一层的结点中，若存在权值大于结点 P 权值的结点 Q，则结点 Q 的兄弟结点中权值较小的一个应该与结点 P 作为左、右子树构造新的二叉树。

综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

对于一组权值都相等的 16 个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（　）。

A. 完全二元树 B. 一般二元树 C. 满二元树 D. 以上都不正确

哈夫曼树 满二叉树

[tag_link]

正确答案：C

哈夫曼树的构造过程中，每次合并都是将两个权值最小的节点合并为一个新的内部节点，因此每个内部节点都恰好有两个子节点，而叶子节点则没有子节点。 根据二叉树的定义，如果一棵二叉树中的每个节点要么是叶子节点（无子节点），要么是有两个子节点的内部节点，那么这棵树称为满二叉树（或称严格二叉树）。 因此，无论权值是否相等，哈夫曼树总是满足这一条件，它必然是一棵满二叉树。

对于本题中权值相等的16个字母，构造出的哈夫曼树同样符合这一性质：每个内部节点都有两个子节点，所以它是一棵满二叉树。 虽然权值相等时，通过特定的合并顺序可能使树的结构更加平衡（例如形成完全二叉树），但满二叉树这一性质是始终成立的。 其他选项如完全二叉树或一般二叉树不一定必然满足，而满二叉树则是哈夫曼树的固有特征，故选项C正确。

给定结点个数 n，在下面二叉树中，叶结点个数不能确定的是（ ）。

A. 满二叉树 B. 完全二叉树 C. 哈夫曼树 D. 二叉排序树

树的概念 哈夫曼树

[tag_link]

正确答案：D

对于给定的结点个数

$n$ ，分析各选项中叶结点个数是否确定。

• 满二叉树若存在，则

$n$ 必须满足 $n=2^h-1$ ，此时叶结点个数为 $2^{h-1}$ ，由 $n$ 唯一确定。

完全二叉树中，叶结点个数为

$\lceil n/2\rceil$ ，也是确定的。

哈夫曼树中，总结点数

$n$ 与叶结点数 $m$ 满足关系 $n=2m-1$ ，因此叶结点数 $m=(n+1)/2$ ，同样由 $n$ 确定。

但在二叉排序树中，对于相同的

$n$ ，可以构造不同形态的树（如平衡树或单支树），叶结点个数会随之变化，因此不能确定。

设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 5 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

(2) 根据你的合并过程，描述N(N≥2)个不等长升序表的合并策略，并说明理由。

哈夫曼树 归并排序

[tag_link]

1）对于长度分别为 m, n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m +n-1 次。故最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。根据上图中的 哈夫曼树，6 个序列的合并过程为：第 1 次合并：表 A 与表 B 合并，生成含有 45 个元素的表 AB ;第 2 次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC;第 3 次合并：表 D 与表 E 合并，生成含有 110 个元素表 DE;第 4 次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE;第 5 次合并：表 ABCDE 与表 F 合并，生成含有 395 个元素的最终表。由上述分析可知，最坏清况下的比较次数为：第 1 次合并，最多比较次数 = 10+35-1 = 44；第 2 次合并，最多比较次数 = 45+40-1 = 84；第 3 次合并，最多比较次数 = 50+60-1 = 109；第 4 次合并，最多比较次数 = 85+110-1 = 194；第 5 次合并，最多比较次数 = 195+200-1 = 394。故比较的总次数最多为：44+84+109+194+394 = 825。

2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。【评分说明】①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5 分。按其他策略进行合并，过程描述正确，给 3 分。②正确算出与合并过程一致的总比较次数，给 2 分。若计算过程正确，但结果错误，可给 1 分。③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给 3 分。如果采用其他策略，只要能够完成合并，给 2 分。