数据结构之树与二叉树的应用

哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

哈夫曼树（Huffman Tree）是一种特殊的二叉树，其主要目的是用于数据压缩。每个结点都有一个权值，表示数据的重要性或频率。哈夫曼树的构建方式确保了具有较高频率的结点距离树根更近，从而减少了整体的带权路径长度（WPL）。

带权路径长度（WPL） 是指从树的根结点到任意叶结点的路径长度与该叶结点的权值的乘积之和。具体定义如下：

$ = _{i=1}^{n} w_i d_i $

其中：

$ w_i $ 是第 $ i $ 个叶结点的权值（表示某种意义的数值，通常与其出现频率相关）。
$ d_i $ 是第 $ i $ 个叶结点到根结点的路径长度（经过的边数）。
$ n $ 是叶结点的总数。

在含有 $ n $ 个带权叶结点的二叉树中，带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。

示例

考虑图 5.18 中的三棵二叉树，均有 4 个叶子结点 $ a, b, c, d $，其权值分别为 7, 5, 2, 4。

第一棵树（图 (a)）：
- $ = 7 + 5 + 2 + 4 = 36 $
第二棵树（图 (b)）：
- $ = 4 + 7 + 5 + 2 = 46 $
第三棵树（图 (c)）：
- $ = 7 + 5 + 2 + 4 = 35 $

其中，图 5.18 (c) 树的 WPL 最小，为 35。这说明它是构成相同叶结点的最优哈夫曼树。

哈夫曼树的构建过程

初始化：
- 将所有叶结点及其权值放入一个优先队列（或小根堆）。
构建树：
- 取出权值最小的两个结点，构建新结点，权值为这两个结点的和，并将新结点放入优先队列。
- 重复上述步骤，直到队列中只剩一个结点，构建完成的树即为哈夫曼树。

哈夫曼编码

哈夫曼编码是基于哈夫曼树生成的编码方案，其特点是：

叶结点的编码是唯一的，且较高频率的字符对应的编码较短，低频字符的编码较长。
通过对字符编码的长度进行优化，哈夫曼编码能有效减少数据的存储空间和传输时间。

编码生成：

从哈夫曼树的根开始，左子树编码为 0，右子树编码为 1，递归地为每个叶结点生成相应的编码。

例如，若字符 $ a, b, c, d $ 的哈夫曼编码分别为 0, 10, 110, 111，则将其组合后进行压缩时，可以显著减少原数据的大小。

并查集

概述

并查集（Union-Find）是一种数据结构，主要用于处理一些不交集的合并及查询问题。它支持以下三种基本操作：

初始化（Initial）: 将集合中的每个元素初始化为独立的单元素子集合。
并集（Union）: 将两个不同的子集合合并为一个子集合，前提是这两个子集合互不相交。
查找（Find）: 查找一个元素所在的子集合，并返回该子集合的根结点。

存储结构

并查集通常使用树（森林）的形式表示，每个子集合用一棵树来表示。具体来说，使用双亲表示法（Parent Array）来存储集合元素：

数组的下标表示元素的名称。
数组的值表示该元素的双亲结点（根结点的双亲指针为负数，表示其为根结点）。

例如，考虑全集合 $ S = $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ $，初始化时每个元素自成一个单元素子集合，数组值均为 -1，表示每个元素都是根结点。

初始化示例

#define SIZE 100
int UFS[SIZE];

void Initial(int s[]) {
    for(int i = 0; i < SIZE; i++) {
        s[i] = -1; // 每个元素自成单元素集合
    }
}

初始化后，双亲表示如下：
1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

操作实现

Find 操作
查找元素 $ x $ 所在的子集合的根结点。

int Find(int s[], int x) {
    while(s[x] >= 0) {
        x = s[x]; // 循环寻找 x 的根
    }
    return x; // 返回根结点
}

Union 操作
合并两个不相交的子集合，前提是 $ Root1 $ 和 $ Root2 $ 不同。

void Union(int s[], int Root1, int Root2) {
    // 要求 Root1 与 Root2 是不同的
    s[Root2] = Root1; // 将 Root2 连接到 Root1 下
}

判断元素是否属于同一集合

要判断两个元素 $ x $ 和 $ y $ 是否属于同一集合，只需分别找到它们的根结点，并比较根结点是否相同。

1
2
3

bool SameSet(int s[], int x, int y) {
    return Find(s, x) == Find(s, y);
}

使用示例

在一系列操作之后，假设我们有如下子集合：

$ S_1 = $0, 1, 2, 3, 4, 5$ $
$ S_2 = $6, 7$ $
$ S_3 = $8, 9$ $

经过合并操作，我们可能得到：

// 合并 S1 和 S2
Union(UFS, Find(UFS, 0), Find(UFS, 6)); // 0 为 S1 的根，6 为 S2 的根

// 合并 S2 和 S3
Union(UFS, Find(UFS, 6), Find(UFS, 8)); // 6 为新的根

并查集的应用

并查集广泛应用于网络连接、图的连通性检测、社交网络中的群组管理等领域。在实际应用中，通常需要进行路径压缩和按秩合并等优化，以提高操作的效率。

路径压缩：在查找操作中，使得沿途的结点直接连接到根结点，以减少树的高度。
按秩合并：在合并操作中，将较小的树连接到较大的树上，保持树的平衡。

选择题

01. 在有 $ n $ 个叶子结点的哈夫曼树中，非叶子结点的总数是（）。

A. $ n-1 $
B. $ n $
C. $ 2n-1 $
D. $ 2n $

答案: A
解析: 根据哈夫曼树的构造过程，哈夫曼树中只有度为 0 和 2 的结点。在非空二叉树中，有公式 $ n_0 = n_2 + 1 $（其中 $ n_0 $ 表示叶子结点个数，$ n_2 $ 表示度为 2 的结点个数），因此，非叶子结点的总数为 $ n - 1 $。

02. 给定整数集合 $3, 5, 6, 9, 12$，与之对应的哈夫曼树是（）。

答案: C
解析: 首先，3 和 5 构造为一棵子树，其根权值为 8，然后该子树与 6 构造为一棵新子树，根权值为 14，再后 9 与 12 构造为一棵子树，最后两子树共同构造为一棵哈夫曼树。

03. 下列编码中，( ) 不是前缀码。

A. $00, 01, 10, 11$
B. $0, 1, 00, 11$
C. $0, 10, 110, 111$
D. $10, 110, 1110, 1111$

答案: B
解析: 若没有一个编码是另一个编码的前缀，则这样的编码称为前缀码。选项 B 中，编码 0 是编码 00 的前缀，1 是编码 11 的前缀，所以 B 选项不是前缀码。

04. 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对（）个字符编码。

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

答案: C
解析:
已知两个字符编码分别为 1 和 01，这说明第二层和第三层各有一个叶子结点。为了使剩余部分的二叉树能对更多字符编码，剩下的二叉树应该是满二叉树。底层可以有 4 个叶子结点，因此还可以对最多 4 个字符编码。

另解：若哈夫曼编码的长度只允许小于等于 4，则哈夫曼树的高度最高是 4。第 3 层已经有一个编码为 01，若全采用 4 位编码，则可以为 0000、0001、0010、0011，因此最多还能编码 4 个字符。

05. 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A. 107
B. 108
C. 214
D. 215

答案: B
解析: 根据哈夫曼树的性质，叶子结点的数量为 $\frac{n+1}{2}$，其中 $n$ 为结点总数。在这棵哈夫曼树中，结点总数 $n = 215$，则叶子结点的数量为 $\frac{215+1}{2} = 108$，因此共有 108 个不同的码字。
【另解】: 哈夫曼树中只有度为 0 和 2 的结点，度为 0 的结点即为叶子结点，因此可以得到 108 个不同的码字。

06. 以下对于哈夫曼树的说法中，错误的是（）。

A. 对应一组权值构造出来的哈夫曼树一般不是唯一的
B. 哈夫曼树具有最小的带权路径长度
C. 哈夫曼树中没有度为 1 的结点
D. 哈夫曼树中除了度为 1 的结点外，还有度为 2 的结点和叶结点

答案: D
解析:

A 选项: 正确。对于一组权值，不同的组合方式可能产生不同的哈夫曼树，但它们的带权路径长度都是最小的，因此哈夫曼树一般不是唯一的。
B 选项: 正确。哈夫曼树的主要性质就是具有最小的带权路径长度。
C 选项: 正确。哈夫曼树中的结点度数只有 0（叶子结点）和 2，没有度为 1 的结点。
D 选项: 错误。哈夫曼树没有度为 1 的结点，所有非叶子结点的度都是 2，叶子结点的度是 0，因此该选项的描述错误。

07. 若度为 $m$ 的哈夫曼树中，叶子结点个数为 $n$，则非叶子结点的个数为（）。

A. $n - 1$
B. $\lceil n/m \rceil - 1$
C. $\lceil (n - 1)/(m - 1) \rceil$
D. $\lceil n/(m - 1) \rceil - 1$

答案: C
解析: 在度为 $m$ 的哈夫曼树中，结点度数要么为 0（叶子结点），要么为 $m$（非叶子结点）。设非叶子结点的个数为 $N_{\text{非叶}}$，叶子结点的个数为 $n$，结点总数为 $N$。由于哈夫曼树有 $n - 1$ 条分支，且每个非叶子结点有 $m$ 条分支，因此满足方程：
$ m N_{} = n - 1 $ 整理得：
$ N_{} = $ 因此答案为 C。

08. 并查集的结构是一种（）。

A. 二叉链表存储的二叉树
B. 双亲表示法存储的树
C. 顺序存储的二叉树
D. 孩子表示法存储的树

答案: B
解析: 并查集的存储结构采用的是双亲表示法存储的树。双亲表示法通过使用一个数组，存储每个结点的父结点的位置，方便进行两个重要操作：查找和合并。

09. 并查集问题与哈夫曼树相关问题

09. 假设初始长度为 10（0~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

答案: C
解析:
初始时，0~9 各自成一个独立的集合。按题目顺序进行操作：

合并 {1} 和 {2}；
合并 {3} 和 {4}；
合并 {5} 和 {6}；
合并 {7} 和 {8}；
合并 {7,8} 和 {9}，得到集合 {7,8,9}；
合并 {1,2} 和 {7,8,9}，得到集合 {1,2,7,8,9}；
合并 {0} 和 {5,6}，得到集合 {0,5,6}；
查找 1-9，发现它们已属于同一个集合，不进行额外操作。

最终的集合为：

{0,5,6}
{1,2,7,8,9}
{3,4}

因此，最终并查集中共有 3 个集合，答案为 C。

10. 下列关于并查集的叙述中，（）是错误的。

A. 并查集是用双亲表示法存储的树
B. 并查集可用于实现克鲁斯卡尔算法
C. 并查集可用于判断无向图的连通性
D. 在长度为 $n$ 的并查集中进行查找操作的时间复杂度为 $O(\log n)$

答案: D
解析:

A: 并查集采用双亲表示法存储树结构，以方便查找父结点，因此 A 正确。
B: 在 Kruskal 算法中，判断是否加入一条边之前，使用并查集可以快速判断两个顶点是否在同一个集合中，从而避免形成回路，B 正确。
C: 并查集用于判断无向图的连通性，通过遍历图的边，将相连的顶点合并为一个集合，C 正确。
D: 并查集查找操作的时间复杂度在最坏情况下为 $O(n)$，并非 $O(\log n)$。如果路径压缩优化和按秩合并，时间复杂度才可以接近 $O(\log^* n)$，因此 D 错误。

11. $n(n>2)$ 个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。

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

答案: A
解析:

A: 哈夫曼树是带权路径长度最小的二叉树，不一定是完全二叉树，因此 A 错误。
B: 哈夫曼树中没有度为 1 的结点，B 正确。
C: 构造哈夫曼树时，总是先选取两个权值最小的结点作为左右子树构造新的二叉树，因此 C 正确。
D: 哈夫曼树中非叶结点的权值等于其左右子树根结点的权值之和，且必定大于等于其左右子树根结点的权值，因此 D 正确。

12. 【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

答案: D
解析:
前缀编码的定义是在一个字符集中，任何一个字符的编码都不能是另一个字符编码的前缀。

A: 没有字符的编码是其他字符编码的前缀，符合前缀编码的定义。
B: 也没有前缀关系，符合前缀编码。
C: 各字符编码之间也没有前缀关系，符合前缀编码。
D: 编码 110 是编码 1100 的前缀，违反了前缀编码的规则，因此 D 不是前缀编码。

13. 【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

答案: D
解析:
在哈夫曼树中，越靠近根结点的权值越大，且同层的结点的权值不会相同。分析每个选项：

A: 两个路径上除了最后的权值（5 和 7）之外，前面的路径权值完全相同，不符合哈夫曼树的性质。
B: 同样，两个路径上前面的权值部分相同（24 和 10），不符合哈夫曼树的性质。
C: 两个路径的权值相差不大，不符合哈夫曼树中结点权值差异较大的性质。
D: 这两个路径上的权值差异较大，并且符合哈夫曼树的性质，因此 D 正确。

14. 【2017 统考真题】

问题: 已知字符集 $a, b, c, d, e, f, g, h$，各字符的哈夫曼编码依次为 0100, 10, 0000, 0101, 001, 011, 11, 0001。则编码序列 0100011001001011110101 的译码结果是 ( )。
A. acgabfh
B. adbagbb
C. afbeagd
D. afeefgd

答案: D
解析: 根据给出的哈夫曼编码依次解码编码序列 0100011001001011110101。

序列可分割为0100011001001011110101，译码结果是afeefgd。

15. 【2018 统考真题】

问题: 已知字符集 $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

答案: A
解析: 通过字符的出现次数构建哈夫曼树，频率越低的字符编码越长，频率越高的字符编码越短。可以通过以左子树为 0、右子树为 1 来进行编码，结果是 A。

16. 【2019 统考真题】

问题: 对 $ n $ 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 $ n $ 的值是 ( )。
A. 56
B. 57
C. 58
D. 60

答案: C
解析: 对 $ n $ 个符号构建哈夫曼树的过程中，会新建 $ n - 1 $ 个结点（双分支结点），因此哈夫曼树的总结点数为 $ 2n - 1 $。
设 $ n $ 为符号个数，则 $ 2n - 1 = 115 $，解得 $ n = 58 $。因此答案为 C。

17. 【2021 统考真题】

问题: 若某二叉树有 5 个叶结点，其权值分别为 10, 12, 16, 21, 30，则其最小的带权路径长度 (WPL) 是 ( )。
A. 89
B. 200
C. 208
D. 289

答案: B
解析: 带权路径长度 (WPL) 是哈夫曼树中的一个重要概念，构造哈夫曼树时，最优 WPL 的计算方法是通过合并两个最小权值结点，直到所有权值都合并完毕。
构造过程如下：

合并权值 10 和 12，得到 22。
合并权值 16 和 21，得到 37。
合并权值 22 和 30，得到 52。
合并权值 37 和 52，得到最终树的权值。

计算 WPL:
$ (10 + 12) + (30 + 16 + 21) = 200 $
因此答案为 B。

程序解答题

问题01: 给定权集 $ w = $5, 7, 2, 3, 6, 8, 9$ $，试构造关于 $ w $ 的一棵哈夫曼树，并求其加权路径长度 $ WPL $。

解答:
构造哈夫曼树的过程如下：

初始权值集: $ $5, 7, 2, 3, 6, 8, 9$ $
第一步: 选取最小的两个权值 $ 2 $ 和 $ 3 $，合并为一个新结点，权值为 $ 2 + 3 = 5 $。
新的权值集为 $ $5, 7, 5, 6, 8, 9$ $。
第二步: 选取最小的两个权值 $ 5 $ 和 $ 5 $，合并为一个新结点，权值为 $ 5 + 5 = 10 $。
新的权值集为 $ $7, 6, 8, 9, 10$ $。
第三步: 选取最小的两个权值 $ 6 $ 和 $ 7 $，合并为一个新结点，权值为 $ 6 + 7 = 13 $。
新的权值集为 $ $8, 9, 10, 13$ $。
第四步: 选取最小的两个权值 $ 8 $ 和 $ 9 $，合并为一个新结点，权值为 $ 8 + 9 = 17 $。
新的权值集为 $ $10, 13, 17$ $。
第五步: 选取最小的两个权值 $ 10 $ 和 $ 13 $，合并为一个新结点，权值为 $ 10 + 13 = 23 $。
新的权值集为 $ $17, 23$ $。
第六步: 最后合并权值 $ 17 $ 和 $ 23 $，得到根结点，权值为 $ 17 + 23 = 40 $。

至此，哈夫曼树构造完毕。

计算加权路径长度 $ WPL $:
带权路径长度 $ WPL $ 是各权值乘以它们到根的路径长度之和：

权值 $ 2 $ 和 $ 3 $ 的路径长度为 4：$ (2 + 3) $
权值 $ 5, 6, 7 $ 的路径长度为 3：$ (5 + 6 + 7) $
权值 $ 8, 9 $ 的路径长度为 2：$ (8 + 9) $

计算 $ WPL $:$ WPL = (2 + 3) + (5 + 6 + 7) + (8 + 9) $ $ WPL = 5 + 18 + 17 = 20 + 54 + 34 = 108 $

因此，带权路径长度 $ WPL = 108 $。

总结: 哈夫曼树的构造过程中虽然可以有不同的树形，但最终的带权路径长度 $ WPL $ 是唯一的。在本题中，最终的 $ WPL = 108 $。

问题02:

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

给出完整的合并过程，并求出最坏情况下比较的总次数。
根据你的合并过程，描述 $ n (n > 2) $ 个不等长升序表的合并策略，并说明理由。

解答:

合并过程
由于合并的表越早参与合并，其数据会在后续的每次合并中再次参与比较。因此，这个问题可以类比为求解最小带权路径长度的问题，类似于哈夫曼树的构造过程。每次选择两个表长度最小的进行合并。具体合并过程如下：

初始表集合为 $ $10, 35, 40, 50, 60, 200$ $：
- 第1步: 选择长度最小的两个表 $ A(10) $ 和 $ B(35) $ 进行合并，生成新的表 $ AB(45) $。$ $45, 40, 50, 60, 200$ $
- 第2步: 选择 $ AB(45) $ 和 $ C(40) $ 进行合并，生成新的表 $ ABC(85) $。$ $85, 50, 60, 200$ $
- 第3步: 选择 $ D(50) $ 和 $ E(60) $ 进行合并，生成新的表 $ DE(110) $。$ $85, 110, 200$ $
- 第4步: 选择 $ ABC(85) $ 和 $ DE(110) $ 进行合并，生成新的表 $ ABCDE(195) $。$ $195, 200$ $
- 第5步: 选择 $ ABCDE(195) $ 和 $ F(200) $ 进行合并，生成最终的表 $ ABCDEF(395) $。

计算最坏情况下的比较总次数:
合并两个长度分别为 $ m $ 和 $ n $ 的表时，最坏情况下需要进行 $ m + n - 1 $ 次比较。各步比较次数如下：

第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 $

结论: 最坏情况下的总比较次数为 825 次。

合并策略:
对于 $ n (n > 2) $ 个不等长升序表进行两两合并时，最优的合并策略是借助哈夫曼树的构造思想，依次选择长度最短的两个表进行合并。这样可以保证最坏情况下的比较次数最少。

理由:
哈夫曼树的构造过程每次选取权值最小的两个节点进行合并，以最小化带权路径长度。同样，对于表的合并问题，每次选择两个最短的表合并可以保证在最坏情况下的比较次数达到最小，从而获得最佳的合并效率。

问题03:

哪种数据结构适宜保存具有前缀特性的不等长编码？
基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。
简述判定某字符集的不等长编码是否具有前缀特性的过程。

解答:

适宜的数据结构:
使用二叉树保存字符集中各字符的编码。每个字符的编码对应于从根结点到某叶结点的路径，路径长度等于编码的位数。叶结点中保存该编码对应的字符。

译码过程:
从左至右依次扫描 0/1 串中的每一位。具体步骤如下：

从二叉树的根开始，根据串中当前位的值进行移动：
- 如果当前位是 0，则沿左子指针移动；
- 如果当前位是 1，则沿右子指针移动。
重复上述移动，直到到达叶结点，输出该叶结点中保存的字符。
然后从根结点重新开始，继续处理剩下的 0/1 串，直到整个串被扫描完毕，译码完成。

示例:
假设有以下字符及其二进制编码：

$ A = 00 $
$ B = 01 $
$ C = 10 $
$ D = 11 $

二进制串 "001011" 可以被译码为 "A B C"。译码过程如下：

从根开始，遇到 "00"，到达叶结点 $ A $，输出 $ A $；
继续扫描，遇到 "10"，到达叶结点 $ C $，输出 $ C $；
继续扫描，遇到 "11"，到达叶结点 $ D $，输出 $ D $。

最终译码结果为 $ ACD $。

判定编码是否具有前缀特性的过程:
要判定某字符集的不等长编码是否具有前缀特性，可以使用二叉树进行构建和检测。具体过程如下：

初始时，二叉树中仅包含一个根结点，左右子指针为空。
依次读入每个编码 $ C $，并从根开始为该编码建立一条路径。对编码 $ C $ 中的每一位执行以下步骤：
- 如果当前位是 0，沿左子指针移动；如果当前位是 1，沿右子指针移动；
- 如果沿移动方向遇到空指针，则创建新结点，并继续沿路径移动；
- 如果移动到某个叶结点（非根），说明当前编码是其他编码的前缀，因此不具有前缀特性，返回失败；
- 如果当前编码的所有位处理完毕时，并没有新建结点，说明该编码是其他编码的前缀，返回失败。
如果所有编码都成功处理完毕且没有发现前缀冲突，则该字符集具有前缀特性。

示例:
对于编码集合：

$ A = 00 $
$ B = 01 $
$ C = 10 $
$ D = 110 $

按照上述过程构建二叉树，并检测前缀特性。

思维扩展

问题:
输入一个整数 data 和一棵二元树。从树的根结点开始往下访问一直到叶结点，打印出路径和路径上节点的值与 data 相等的所有路径。使用前序遍历递归算法。

解答思路:

前序遍历:
使用前序遍历的递归算法，从根结点开始访问每个结点，依次将结点加入路径。如果到达叶结点，检查路径上的结点值之和是否等于 data。如果等于，打印路径。
栈或数组保存路径:
我们可以使用一个数组或栈来保存当前路径。当递归遍历到叶子结点时，检查当前路径上的结点值之和是否等于 data。如果是，则输出该路径。
递归回溯:
在递归返回之前，要将当前结点的值从路径中移除，以便回溯到父结点后继续处理其他分支。

算法步骤:

创建一个递归函数 findPaths，该函数接受当前结点、路径列表、当前路径的和以及目标值 data 作为参数。
使用前序遍历：每到达一个结点时，将该结点的值加入当前路径并更新路径的和。
如果该结点是叶结点，并且路径和等于 data，则打印该路径。
继续递归访问左右子树。
当递归返回父结点时，从路径中移除当前结点的值，继续处理其他分支。

#include <iostream>
#include <vector>

using namespace std;

// 二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历查找路径的递归函数
void findPaths(TreeNode* node, vector<int>& currentPath, int currentSum, int targetSum) {
    if (!node) return; // 如果节点为空，返回

    // 将当前节点的值加入路径中
    currentPath.push_back(node->val);
    currentSum += node->val;

    // 检查当前节点是否为叶子节点且路径和是否等于目标值
    if (!node->left && !node->right && currentSum == targetSum) {
        cout << "路径: ";
        for (int val : currentPath) {
            cout << val << " ";
        }
        cout << endl;
    }

    // 递归访问左右子树
    findPaths(node->left, currentPath, currentSum, targetSum);
    findPaths(node->right, currentPath, currentSum, targetSum);

    // 回溯：在返回父节点之前移除当前节点的值
    currentPath.pop_back();
}

// 主函数：调用递归函数查找所有路径
void findAllPaths(TreeNode* root, int data) {
    vector<int> currentPath; // 当前路径
    findPaths(root, currentPath, 0, data);
}

// 测试程序
int main() {
    // 构建示例树
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(5);
    root->right = new TreeNode(12);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(7);

    // 输入目标和
    int data = 22;
    findAllPaths(root, data);

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

数据结构之树与二叉树的应用

数据结构之树与二叉树的应用

哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

示例

哈夫曼树的构建过程

哈夫曼编码

并查集

概述

存储结构

初始化示例

操作实现

判断元素是否属于同一集合

使用示例

并查集的应用

选择题

01. 在有 $ n $ 个叶子结点的哈夫曼树中，非叶子结点的总数是（）。

02. 给定整数集合 \(3, 5, 6, 9, 12\)，与之对应的哈夫曼树是（）。

03. 下列编码中，( ) 不是前缀码。

04. 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对（）个字符编码。

05. 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

06. 以下对于哈夫曼树的说法中，错误的是（）。

07. 若度为 \(m\) 的哈夫曼树中，叶子结点个数为 \(n\)，则非叶子结点的个数为（）。

08. 并查集的结构是一种（）。

09. 并查集问题与哈夫曼树相关问题

10. 下列关于并查集的叙述中，（）是错误的。

11. \(n(n>2)\) 个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。

12. 【2014 统考真题】

13. 【2015 统考真题】

14. 【2017 统考真题】

15. 【2018 统考真题】

16. 【2019 统考真题】

17. 【2021 统考真题】

程序解答题

问题01: 给定权集 $ w = \(5, 7, 2, 3, 6, 8, 9\) $，试构造关于 $ w $ 的一棵哈夫曼树，并求其加权路径长度 $ WPL $。

问题02:

问题03:

思维扩展

数据结构之树与二叉树的应用

哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

示例

哈夫曼树的构建过程

哈夫曼编码

并查集

概述

存储结构

初始化示例

操作实现

判断元素是否属于同一集合

使用示例

并查集的应用

选择题

01. 在有 $ n $ 个叶子结点的哈夫曼树中，非叶子结点的总数是（）。

02. 给定整数集合 \(3, 5, 6, 9, 12\)，与之对应的哈夫曼树是（）。

03. 下列编码中，( ) 不是前缀码。

04. 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对（ ）个字符编码。

05. 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

06. 以下对于哈夫曼树的说法中，错误的是（ ）。

07. 若度为 \(m\) 的哈夫曼树中，叶子结点个数为 \(n\)，则非叶子结点的个数为（ ）。

08. 并查集的结构是一种（ ）。

09. 并查集问题与哈夫曼树相关问题

10. 下列关于并查集的叙述中，（ ）是错误的。

11. \(n(n>2)\) 个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。

12. 【2014 统考真题】

13. 【2015 统考真题】

14. 【2017 统考真题】

15. 【2018 统考真题】

16. 【2019 统考真题】

17. 【2021 统考真题】

程序解答题

问题01: 给定权集 $ w = \(5, 7, 2, 3, 6, 8, 9\) $，试构造关于 $ w $ 的一棵哈夫曼树，并求其加权路径长度 $ WPL $。

问题02:

问题03:

思维扩展

04. 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还最多可对（）个字符编码。

05. 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

06. 以下对于哈夫曼树的说法中，错误的是（）。

07. 若度为 \(m\) 的哈夫曼树中，叶子结点个数为 \(n\)，则非叶子结点的个数为（）。

08. 并查集的结构是一种（）。

10. 下列关于并查集的叙述中，（）是错误的。

11. \(n(n>2)\) 个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。