注意
## 注意
左分支和右分支分别表示 0 还是 1 并无强制规定。因此构造出的哈夫曼树在形态上可能不唯一。此外，当存在多个权值相同的结点时，合并顺序的不同也可能导致结构不同的哈夫曼树。但无论其体形态如何，其带权路径长度 WPL 始终相同且达到最小值，即最优性不受影响。
<!-- page: 195 -->
第5章 树与二叉树
183
## 5.5.2 并查集
### 1. 并查集的概念
并查集是一种处理不相交集合的合并与查询问题的树状数据结构，它支持三种基本操作：
1）Initial(S)：将集合S中的每个元素都初始化为一个独立的单元素子集合。
2）Union(S, Root1, Root2)：将集合 S 中的子集合 Root2 并入子集合 Root1。要求 Root1 和 Root2 属于不同的子集合，否则不执行合并操作。
3）Find(S, x)：在集合 S 中查找单元素 x 所属的子集合，并返回该子集合的根结点。
### 2. 并查集的存储结构
并查集通常采用树的双亲表示法作为其存储结构：每个子集合用一棵树来表示，所有子集合对应的树共同构成一个森林，并统一存储在一个数组中。在该数组中，数组下标代表集合中的元素编号，而每个元素所存的值为其双亲结点的下标；对于根结点，其双亲域设为负数——通常取该子集合元素数量的相反数，既标识其为根，又记录了集合的规模。
例如，设有一个全集合为 $S = \{0,1,2,3,4,5,6,7,8,9\}$，初始化时每个元素自成一个单元素子集合，对应数组中每个位置的值均为 -1，如图 5.28 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.28 并查集的初始化
经过若干合并操作后，这些子集合可能被合并为三个更大的子集合：$S_1 = \{0,6,7,8\}$，$S_2 = \{1,4,9\}$，$S_3 = \{2,3,5\}$，此时并查集的树形及其对应的数组存储形式如图 5.29 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 集合的树形表示 (b) 集合 $S_1$，$S_2$ 和 $S_3$ 的(森林)双亲表示
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.29 用树表示并查集 要实现两个子集合的并操作（$S_1 \cup S_2$），只需将其中一个子集合根结点在数组中的值设为另一个子集合的根结点下标。例如，将 $S_2$ 的根指向 $S_1$ 的根后，所得结构如图 5.30 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 5.30 $S_1 \cup S_2$ 的表示方法 在该存储方案中，集合元素的编号从 0 到 SIZE-1，其中 SIZE 表示集合中元素的最大数量。 ### 3. 并查集的基本实现 并查集的结构定义如下：将每个元素对应的数组值设为 -1，表示这些元素各自为根。 （2）并查集的 Find 操作 在并查集中查找并返回包含元素 x 的树的根。#define SIZE 100 int UFSets[SIZE]; //集合元素数组（双亲指针数组） <!-- page: 196 --> 2027年数据结构考研复习指导 下面是并查集主要运算的实现。 （1）并查集的初始化操作 ```c void Initial(int S[]) { // S 即并查集 for (int i = 0; i &lt; SIZE; i++) // 每个自成一个单元素集合 S[i] = -1; }判断两个元素是否属于同一集合，只需分别找到它们的根，再比较根是否相同即可。 （3）并查集的 Union 操作 合并两个不相交子集合的操作。当要合并两个元素所在的集合时，需要先找到这两个元素的根，然后让一棵子集树的根指向另一棵子集树的根。int Find(int S[], int x) { while (S[x] &gt;= 0) // 循环寻找 x 的根 x = S[x]; return x; // 根的 S[] 小于 0 }Find 和 Union 操作的时间复杂度分别为 $O(d)$ 和 $O(1)$，其中 $d$ 为树的深度。 ## 4. 并查集实现的优化 在极端情况下，由 $n$ 个元素构成的集合树可能退化为一条链，深度达到 $n$，此时 Find 操作的最坏时间复杂度为 $O(n)$。改进的办法是：在执行 Union 操作前先比较两个子集合的规模，将规模较小的树作为子树挂到规模较大的树的根下，即“小树并入大树”。为此，可利用根结点的绝对值（其绝对值即为集合大小）来记录该集合中包含的元素个数。 （1）改进的 Union 操作 采用这种按集合大小合并的策略后，所构造的集合树深度不超过 $\lfloor \log_2 n \rfloor + 1$。 然而，随着子集不断合并，集合树的深度仍可能逐渐增大。为进一步缩短查找时间，还可对上述 Find 操作进一步优化：引入路径压缩机制——在找到根结点后，将从 x 到根路径上的所有中间结点直接挂接到根结点下，从而“压平”整条路径。 （2）改进的 Find 操作 采用按大小合并与路径压缩两种优化后，并查集的操作效率得到极大提升，使得集合树的深度不超过 $O(\alpha(n))$，其中 $\alpha(n)$ 是一个增长极其缓慢的函数，对于常见的正整数 $n$，通常 $\alpha(n) \leqslant 4$。 关于并查集的实际应用示例，请参见本书配套视频。 ## 5.5.3 本节试题精选 ### 一、单项选择题 01. 在有 $n$ 个叶结点的哈夫曼树中，非叶结点的总数是（ ）。 A. $n - 1$ B. $n$ C. $2n - 1$ D. $2n$ 02. 给定整数集合 $\{3,5,6,9,12\}$，与之对应的哈夫曼树是（ ）。void Union(int S[], int Root1, int Root2) { if (Root1 == Root2) return; // 要求 Root1 与 Root2 是不同的集合 S[Root2] = Root1; // 将根 Root2 连接到另一根 Root1 下面 }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D.
03. 下列编码中，（ ）不是前缀码。
A. $\{00, 01, 10, 11\}$
B. $\{0, 1, 00, 11\}$
C. $\{0, 10, 110, 111\}$
D. $\{10, 110, 1110, 1111\}$
04. 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对（ ）个字符编码。
A. 2
B. 3
C. 4
D. 5
05. 一裸哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A. 107
B. 108
C. 214
D. 215
06. 设某哈夫曼树有 5 个叶结点，则该哈夫曼树的高度最高可以是（ ）。
A. 3
B. 4
C. 5
D. 6
07. 以下对于哈夫曼树的说法中，错误的是（ ）
A. 用一组权值构造出的哈夫曼树可能不唯一，但带权路径长度唯一
B. 哈夫曼树具有最小的带权路径长度
C. 哈夫曼树中没有度为 1 的结点
D. 哈夫曼树中除了度为 1 的结点，还有度为 2 的结点和叶结点
08. 下列关于哈夫曼树的说法中，错误的是（ ）。
I. 哈夫曼树的总结点数不能是偶数
II. 哈夫曼树中度为 1 的结点数等于度为 2 和 0 的结点数之差
III. 哈夫曼树的带权路径长度等于其所有分支结点的权值之和
A. 仅 III
B. I 和 II
C. 仅 II
D. I、II 和 III
<!-- page: 198 -->
2027年数据结构考研复习指导
09. 若度为 $m$ 的哈夫曼树中，叶结点数为 $n$，则非叶结点的个数为（ ）。
A. $n - 1$
B. $\lfloor n / m \rfloor - 1$
C. $\lceil (n - 1) / (m - 1) \rceil$
D. $\lceil n / (m - 1) \rceil - 1$
10. 并查集的结构是一种（ ）。
A. 二叉链表存储的二叉树
B. 双亲表示法存储的树
C. 顺序存储的二叉树
D. 孩子表示法存储的树
11. 并查集中最核心的两个操作是：① 查找，查找两个元素是否属于同一个集合；② 合并，若两个元素不属于同一个集合，且所在的两个集合互不相交，则合并这两个集合。假设初始长度为 $10(0 \sim 9)$ 的并查集，按 $1-2$、$3-4$、$5-6$、$7-8$、$8-9$、$1-8$、$0-5$、$1-9$ 的顺序进行查找和合并操作，最终并查集共有（ ）个集合。
A. 1
B. 2
C. 3
D. 4
12. 下列关于并查集的说法中，正确的是（ ）（注，本题涉及图的考点）。
A. 并查集不能检测图中是否存在环路的问题
B. 通过路径优化后的并查集在最坏情况下的高度仍是 $O(n)$
C. Find 操作返回集合中元素个数的相反数，它用来作为某个集合的标志
D. Union 操作时可根据当前集合的规模，将小集合合并到大集合中
13. 下列关于并查集的叙述中，（ ）是错误的（注意，本题涉及图的考点）。
A. 并查集是用双亲表示法存储的树
B. 并查集可用于实现克鲁斯卡尔算法
C. 并查集可用于判断无向图的连通性
D. 在长度为 $n$ 的并查集中进行查找操作的时间复杂度为 $O(\log_2 n)$
14. 【2010 统考真题】$n$（$n \geqslant 2$）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任意一个非叶结点的权值一定不小于下一层任意一个结点的权值
15. 【2014 统考真题】5 个字符有如下 4 种编码方案，不是前缀编码的是（ ）。
A. 01,0000,0001,001,1
B. 011,000,001,010,1
C. 000,001,010,011,100
D. 0,100,110,1110,1100
16. 【2015 统考真题】下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
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
17. 【2017 统考真题】已知字符集 $\{\mathrm{a},\mathrm{b},\mathrm{c},\mathrm{d},\mathrm{e},\mathrm{f},\mathrm{g},\mathrm{h}\}$，各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，编码序列 0100011001001011110101 的译码结果是（ ）。
A. acgabfh
B. adbagbb
C. afbeagd
D. afeefgd
18. 【2018 统考真题】已知字符集 $\{\mathrm{a},\mathrm{b},\mathrm{c},\mathrm{d},\mathrm{e},\mathrm{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
<!-- page: 199 -->
第5章 树与二叉树
187
19. 【2019 统考真题】对 $n$ 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 $n$ 的值是（ ）。
A. 56
B. 57
C. 58
D. 60
20. 【2021 统考真题】若某二叉树有 5 个叶结点，其权值分别为 10, 12, 16, 21, 30，则其最小的带权路径长度（WPL）是（ ）。
A. 89
B. 200
C. 208
D. 289
21. 【2022 统考真题】对任意给定的含 $n$（$n > 2$）个字符的有限集 $S$，用二叉树表示 $S$ 的哈夫曼编码集和定长编码集，分别得到二叉树 $T_{1}$ 和 $T_{2}$。下列叙述中，正确的是（ ）。
A. $T_{1}$ 与 $T_{2}$ 的结点数相同
B. $T_{1}$ 的高度大于 $T_{2}$ 的高度
C. 出现频次不同的字符在 $T_{1}$ 中处于不同的层
D. 出现频次不同的字符在 $T_{2}$ 中处于相同的层
22. 【2023 统考真题】在由 6 个字符组成的字符集 $S$ 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 $S$ 构造的哈夫曼编码的加权平均长度为（ ）。
A. 2.4
B. 2.5
C. 2.67
D. 2.75
23. 【2025 统考真题】设字符集 $S$ 中包含 7 个字符，各字符出现的频次分别为 2, 3, 4, 6, 8, 10, 11。现为 $S$ 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符数是（ ）。
A. 2
B. 3
C. 4
D. 5
## 二、综合应用题
01. 设给定权集 $w = \{5, 7, 2, 3, 6, 8, 9\}$，试构造关于 $w$ 的一棵哈夫曼树，并求其加权路径长度 WPL。
02. 【2012 统考真题】设有 6 个有序表 A, B, C, D, E, F，分别含有 10, 35, 40, 50, 60 和 200 个数据元素，各表中的元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并为 1 个升序表，并使最坏情况下比较的总次数达到最小。请回答下列问题：
1）给出完整的合并过程，并求出最坏情况下比较的总次数。
2）根据你的合并过程，描述 $n$（$n \geqslant 2$）个不等长升序表的合并策略，并说明理由。
03. 【2020 统考真题】若任意一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 $\geqslant 2$）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 $L$ 位，且具有前缀特性。请回答下列问题：
1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？
2）基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。
3）简述判定某字符集的不等长编码是否具有前缀特性的过程。
## 5.5.4 答案与解析
### 一、单项选择题
#### 01. A
由哈夫曼树的构造过程可知，哈夫曼树中只有度为 0 和 2 的结点。在非空二叉树中，有 $n_0 = n_2 + 1$，所以 $n_2 = n - 1$。
【另解】$n$ 个结点构造哈夫曼树需要 $n - 1$ 次合并过程，每次合并新建一个分支结点，所以选择选项 A。
#### 02. C
首先，3 和 5 构造为一棵子树，其根权值为 8，然后该子树与 6 构造为一棵新子树，根权值
<!-- page: 200 -->
2027年数据结构考研复习指导
为 14，再后 9 与 12 构造为一棵子树，最后两棵子树共同构造为一棵哈夫曼树。
03. B
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。在选项 B 中，0 是 00 的前缀，1 是 11 的前缀。
04. C
在哈夫曼编码中，一个编码不能是任何其他编码的前缀。3 位编码可能是 001，对应的 4 位编码只能是 0000 和 0001。3 位编码也可能是 000，对应的 4 位编码只能是 0010 和 0011。若全采用 4 位编码，则可以为 0000, 0001, 0010 和 0011。题中问的是最多，所以选择选项 C。
【另解】若哈夫曼编码的长度只允许小于或等于 4，则哈夫曼树的高度最高是 5，已知一个字符编码为 1，另一个字符编码为 01，这说明第二层和第三层各有一个叶结点，为使得该树从第 3 层起能够对尽可能多的字符编码，余下的二叉树应该是满二叉树，如右图所示，底层可以有 4 个叶结点，最多可以再对 4 个字符编码。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
05. B 根据上题的结论，叶结点数为 $(215 + 1)/2 = 108$，所以共有 108 个不同的码字。 【另解】在哈夫曼树中只有度为 0 和 2 的结点，结点总数 $n = n_0 + n_2$，且 $n_0 = n_2 + 1$，由题知 $n = 215$，$n_0 = 108$。 06. C 在哈夫曼树的构造中，每个初始结点最终都成为叶结点，5 个初始结点构造的哈夫曼树共新建 4 个双分支结点，4 个双分支结点所构成的高度最高的哈夫曼树如右图所示，其高度为 5。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
07. D
在哈夫曼树的构造过程中，每次选根的权值最小的两棵树，一棵作为左子树，一棵作为右子树，生成新的二叉树，新的二叉树根的权值应为其左右两棵子树根结点权值的和。至于谁做左子树，谁做右子树，没有限制，所以构造的哈夫曼树是不唯一的，但其带权路径长度是最小的和唯一的。哈夫曼树只有度为 0 和 2 的结点，度为 0 的结点是外结点，带有权值，没有度为 1 的结点。
08. C
由 $n$ 个初始结点构造的哈夫曼树，会新建 $n - 1$ 个双分支结点，因此总结点数为 $2n - 1$，必为奇数，说法 I 正确。哈夫曼树中没有度为 1 的结点，说法 II 错误。哈夫曼的带权路径长度有两种计算方法：① 所有叶结点的带权路径长度之和；② 所有分支结点的权值之和，说法 III 正确。
09. C
一棵度为 $m$ 的哈夫曼树应只有度为 0 和 $m$ 的结点，设度为 $m$ 的结点有 $n_m$ 个，度为 0 的结点有 $n_0$ 个，又设结点总数为 $N$，$N = n_0 + n_m$。因 $N$ 个结点的哈夫曼树有 $N - 1$ 条分支，则 $mn_m = N - 1 = n_m + n_0 - 1$，整理得 $(m - 1)n_m = n_0 - 1$，$n_m = (n_0 - 1)/(m - 1)$。
10. B
并查集的存储结构是用双亲表示法存储的树，主要是为了方便两个重要的操作。
11. C
初始时，0～9 各自成一个集合。查找 1-2 时，合并 $\{1\}$ 和 $\{2\}$；查找 3-4 时，合并 $\{3\}$ 和 $\{4\}$；
<!-- page: 201 -->
第5章 树与二叉树
189
查找 5-6 时，合并{5}和{6}；查找 7-8 时，合并{7}和{8}；查找 8-9 时，合并{7, 8}和{9}；查找 1-8 时，合并{1, 2}和{7, 8, 9}；查找 0-5 时，合并{0}和{5, 6}；查找 1-9 时，它们属于同一个集合。最终的集合为{0, 5, 6}、{1, 2, 7, 8, 9}和{3, 4}，因此答案选择选项 C。