5.5 树和二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

前缀编码：一条路径上只有一种编码。

哈夫曼树只有度为 0 和 n 的结点，是严格 n 叉树，可以补充 0 结点。

每个子集合是一棵树，并查集是一个森林。

双亲表示法能方便并和查

并：时间复杂度 O(1)

小并大

查：时间复杂度 O(n)

并查集结构定义：并查集本质上是一个双亲指针数组。

int UFSets[10]; // 双亲指针数组

初始化

void Initial(int *S)
{
    for (int i = 0; i < 10; i++)
    {
        S[i] = -1;
    }
}

查找根

int Find(int *S, int x)//查找 x 的根
{
    while (S[x] >= 0)//当 x 的双亲不是根时
    {
        x = S[x];
    }
    return x;
}

合并两个集合

void Union(int *S, int Root1, int Root2)
{
    if (Root1 == Root2)
    {
        return;
    }
    S[Root2] = Root1;
}