哈夫曼树并查集

（1）哈夫曼树

特殊概念：

1.结点的权：表示结点树的重要性

2.带权路径长度：从树的根到该节点的路径长度（经过的边数）与该节点上权值的乘积

2.树的带权路径长度：该树的所有叶子节点的带权路径长度之和

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

哈夫曼编码：

固定长度编码——每个字符用相等长度的二进制位表示

可变长度编码——允许对不同字符用不等长度的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

有哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值

（2）并查集

用互不相交的树，表示多个“集合”

查一个元素属于哪个集合：可以从指定元素出发，一路向北，找到根结点，判断两个结点是否属于同一个集合，分别查找两个元素的根结点，判断是否相同

把两个集合合并为一个集合：让一棵树成为另一颗树的子树即可

双亲表示法更适合实现并查集

# define maxsize 100  //树中最多结点数
typedef struct {      //树中结点定义
    int data;         //数据元素
    int parent;       //双亲位置域
}ptnode;
typedef struct {      //数的类型定义
    ptnode nodes[maxsize];//双亲表示
    int n;            //结点数
}ptree;

 并查操作代码

//find查操作，找x所属集合（返回x所属根结点）
int find(int s[], int x) {
    while (s[x] >= 0)
        x = s[x];
    return x;
}
//union并操作，将两个集合合并为一个
void union(int s[], int root1, int root2) {
    //要求root1与root2是不同的集合
    if (root1 == root2)return;
    //将根root2链接到另一根root1下面
    s[root2] = root1;
}

并的时间复杂度为O(1)，查的最坏时间复杂度为O(n)。

合并时让小树成为大树的子树，让高度增加的没那么快

可以用根结点的绝对值表示树的结点总数

并操作优化后代码

void union(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 {
        s[root2] += s[root1];    //累加结点总数
        s[root1] = root2;        //小数合并到大树
    }
}

查操作优化后代码

//find查操作优化，先找到根结点，再进行“压缩路径”
int find(int s[], int x) {
    int root = x;
    while (s[root] >= 0)root = s[root];//循环找到根
    while (x != root) {      //压缩路径
        int t = s[x]           //t指向x的父节点
            s[x] = root;       //x直接挂到根结点下
        x = t;
    }

    return root;          //返回根结点编号
}