哈夫曼树

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

树的带权路径长度WPL：所有从根节点到叶结点的路径长度与结点权值乘积(经过的边数)之和

其中：w_i是第i个叶节点所带权值，l_i是该叶节点到根节点的路径长度

构造

1. 将n个带权结点分别作为n棵只含一个结点的二叉树，树的集合作为森林F
2. 构造一个新节点，从F中选取最小的两个带权结点，作为新节点的左右孩子，新节点的权值即为两个孩子权值之和
3. 从F中删除2中被选中的两个树，并将新得到的树加入森林F
4. 重复上述步骤直到F中只剩下1棵树

特性

• 每个初始节点最终都将成为叶子节点，且权值越小的结点离根节点的路径长度越大。
• 哈夫曼树的结点总数为2n-1。
• 哈夫曼树中不存在度为1的结点。
• 哈夫曼树并不唯一，但WPL必然相同且为最优。

哈夫曼编码

基于哈夫曼树构造的一种编码方式。

适用于带权的一些问题场景或优化(比如数据压缩等)

对字符集的编码：

1. 将字符集中每个字符作为一个叶子节点，各个字符出现的频度作为结点的权值
2. 构造哈夫曼树

算出哈夫曼树的WPL即可作为该字符集的二进制编码位数，从而得出压缩率

每个字符的二进制表示：从根节点出发到叶子节点看，0和1表示左子树还是右子树将由题目给出

并查集

一种简单的集合表示法，支持三种操作：

1. 初始化Initial(S)：将集合S中每一项元素初始化为一个只有单元素的自己和
2. 并集Union(S,root1,root2)：把集合S中的子集root2并入子集合root1，要求root1和root2不相交，否则不合并
3. Find(S,x)在集合S中查找元素x所在的子集合，返回子集和的根节点

通常用树的双亲作为并查集的数据结构，以数组下标表示元素本身，数组元素值为根节点的值，根节点的下标为子集合名，根节点的双亲由负数表示

代码表示

1
2
3
4
5
6
7

//初始化
#define size 100
void Initial(int *s){
    for(int i = 0;i<size;i++){
        s[i] = -1; //初始化中每个结点都是根节点，为负值
    }
}

1
2
3
4
5
6

int find(int *s,int x){
    while(s[x]>0){ //循环查找x的根节点
        x = s[x];
    }
    return x; //此时x为负值，找到了根节点，返回
}

1
2
3

void Union(int *s,int root1,int root2){
    s[root2] = root1; //将根节点root2连接root1下
}