#数据结构 #C
【结点的权】
有某种现实含义的数值（如：表示结点的重要性等）。
【结点的带权路径长度】
从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。
【树的带权路径长度】
树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）。
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。如图，最最右侧两个二叉树中，均属于哈夫曼树（Huffman Tree）。
注意，这里只计算叶子结点。
给定n个权值分别为
- 将这
n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。 - 构造一个新结点，从
F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新 结点的权值置为左、右子树上根结点的权值之和。 - 从
F中删除刚才选出的两棵树，同时将新得到的树加入F中。 - 重复步骤（2）和（3），直至
F中只剩下一棵树为止。
特点：
- 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
- 哈夫曼树的结点总数为
2n − 1。 - 哈夫曼树中不存在度为1的结点。
- 哈夫曼树并不唯一，但
$WPL$ 必然相同且为最优。
以{3,2,1,7,2}为例，有两种哈夫曼树的生成方式，且带权路径长度之和均为最小。
在战争片中经常看到发送接收电报信息，电报信息通常只有0和1，问题，如何通过对给定长度的信息， 设计一种优秀的编码方式？
【问题】 例如有100道选择题，答案可能是A、B、C、D中的一种，那么我如何将这100道题目的答案传出去？ 【解决方法】
- 可采用ASCII编码，采用8位置表示一个答案。
| A | B | C | D |
|---|---|---|---|
| 0100 0001 | 0100 0010 | 0100 0011 | 0100 0100 |
这样的编码方式，略显冗余，因为，要使用
- 直接使用两位表示：
| A | B | C | D |
|---|---|---|---|
| 00 | 01 | 10 | 11 |
将传输信息量直接压缩到
- 使用哈夫曼编码，即下表，
| A | B | C | D |
|---|---|---|---|
| 10 | 111 | 0 | 110 |
将使用信息：
【可变长度编码】 允许对不同字符用不等长的二进制位表示。 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
由哈夫曼树得到哈夫曼编码，需要满足：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。 哈夫曼编码使用的方式，降低二进制编码的数量，因此哈夫曼编码可用于数据压缩。
对于数据的逻辑结构，有一种之前尚未提及的“集合”（set）。集合，是一种互斥、有限、确定的一类数据的总称，例如某个班级内的同学。 集合，可以依据某种依据，将其划分成不同的子集，子集与子集之间，互不相交。如何使用代码来表达集合直接的关系？
联想到之前的森林，是m（m ≥ 0）棵互不相交的树的集合。可以通过转化，将集合转化成森林，于是集合中的某一个子集的元素，可以组织成树。
- 对于给定元素，怎么判断其在哪一个集合？ 对于指定元素，一路指向父结点，最后找到树的根结点。标志其所在的集合。
- 给定两个元素，判断是否属于同一个集合？ 对于两个元素，分别找寻其跟结点，判断二者根结点是否相同。
集合的合并，即将一个树的根结点，指向另一个树的根结点。
并查集（Disjoint-set data structure），用集合中的一个元素代表集合。在本质上，属于“集合”这一种逻辑结构，属于可以合并并且可以查找的集合。
树的存储方式有三种类型：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
其中，双亲表示法最合适用于并查集，因为合并和查找的实现相对而言更加方便，所有的指向都是向父结点上指。 在双亲表示法中，每个结点中保存指向双亲的“指针”。
// 树中最多的结点
#define MAX_TREE_SIZE 100
typedef struct { // 树的结点定义
ElemType data; // 数据元素
int parent; // 双亲位置域
} PTNode;
typedef struct { // 树的类型定义
PTNode node[MAX_TREE_SIZE]; // 双亲表示
int n; // 结点树
} PTree;
上述树结构，可以使用这个表格中的数据结点表示。
| 数组下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
| 6 | G | 2 |
| 7 | H | 3 |
| 8 | I | 3 |
| 9 | J | 3 |
| 10 | K | 4 |
| 11 | ... | ... |
其中，根结点固定存储在0，-1表示没有双亲。 对于集合而言，也可以用同样的表示方法：
例如，K的S[]中的值是4，表示其父结点为数组下标为4的结点，即E；E的S[]中的值是1，表示其父结点为数组下标为1的结点，即B；B的S[]中的值是0，表示其父结点为数组下标为0的结点，即A；A的S[]中的值是-1，表示其为根结点，不可以再进行追溯。所以，K结点是属于A集合内部的元素。
#define SIZE 13
int S[SIZE] = {0}; // 集合元素数组
// 初始化并查集
void Initial(int S[])
{
for (int i = 0; i < SIZE; i++) {
S[i] = -1;
}
}
初始化的时候均将其集合元素数组设置成-1，表示其没有任何子集关系。
// Find 查操作，找x所属的集合
int Find(int S[], int x)
{
while(S[x] >= 0) {
x = S[x];
}
return x;
}循环查找S[i]的值，一直到该值小于0为止，即查找到其所在的根结点了，返回根结点的序号。
// Union 并操作
void Union(int S[], int root1, int root2)
{
// 要求Root1与Root2是不同集合
if (root1 == root2) {
return;
}
S[root2] = root1;
}
- Union 合并操作，由于对数组直接操作，时间复杂度：
$O(1)$ - Find 查找，需要遍历循环，最坏时间复杂度：$O(N)$
由于并查集的查找复杂度取决于树的高度，那么为了优化查找效率，在合并并查集的时候，每次Union的过程中，决定让小的树合并到大的树，这种合并叫按秩合并，某结点的秩是该结点的高度上界。
优化思路：
- 使用根结点
S[i]的绝对值，表示树的结点总数，注意，这个值是负数； - 比较两个
root的s[i]的绝对值，让小树合并到大树。
程序实现：
// Union 并操作，让矮树合并到高树
void UnionByRank(int S[], int root1, int root2)
{
// 要求Root1与Root2是不同集合
if (root1 == root2) {
return;
}
if (S[root2] > S[root1]) { // root2 结点数量更少
S[root1] += S[root2]; // 累计结点总数
S[Root2] = root1; // 小树合并大数
} else { // root1 结点数量更少
S[root2] += S[root1]; // 累计结点总数
S[Root1] = root2; // 小树合并大数
}
}优化后的Union操作，可以使得整个构造的树的高度不会超过：
// Find 查操作，先找到根结点，再压缩路径
int Find(int S[], int x)
{
int root = x; // 原结点的序列
int tmp = x;
while(S[root] >= 0) {
root = S[root];
}
// 压缩路径，循环开始，直至追溯到根结点为止
while (tmp != root) {
// 使用parent临时存储当前结点的父结点，在本次循环结束的时候，再更新到tmp
int parent = S[tmp]; // parent 指向 tmp 的父结点
S[tmp] = root; // tmp 直接挂到根结点下
tmp = parent;
}
return root; // 返回根结点编号
}对于每次并查集的操作，先按秩合并，在路径压缩，可以使得树的高度保持在较低的数值。使得查找、合并的时间消耗都大大降低。