哈夫曼树

哈夫曼树的定义

  • 是最优二叉树，即WPL（带权路径长度）最小的树
  • 带权路径长度：每个叶子结点的权值为$W{k}$，根节点到每个叶子结点的长度是$L{k}$，则整个树的带权路径长度就是每个叶子结点的带权路径长度之和：WPL=$\sum{k=1}^{n}W{k}L_{k}$

哈夫曼树的特点

  • 树中只有度为0和度为2的结点
  • n个叶子结点的哈夫曼树节点总数是2n-1
  • 左右子树交换仍是哈夫曼树
  • 同一组权值会出现不同构的哈夫曼树

哈夫曼树的构造

  • 需要用到堆排序
  • 每次取权值最小的两棵二叉树合并并将权值之和放回堆中
  • 依次进行合并直到堆空为止
  • 总体时间复杂度为O(nlogn)

哈夫曼编码

哈夫曼编码的特点

  • 一种前缀码，即任何一个字符编码都不是另一字符编码的前缀

哈夫曼编码的构造

  • 二叉树的左分支为0，右分支为1
  • 字符只出现在叶节点上
  • 可以使用哈夫曼树进行构造，所得到的哈夫曼编码代价最小

集合

集合的运算

  • 交、并、补、差、判定元素属于哪个集合

并查集

可以使用树来表示（以下使用数组存储的树）

数组结构

typedef struct{
    ElementType Data;
    int parent;
}SetType;

并查集存储形式

下标 Data parent
0 1 -1
1 2 0
2 3 -1
3 4 0
4 5 2
5 6 -1
6 7 0
7 8 2
8 9 5
9 10 5

查找某个元素所在集合

int Find(SetType S[],ElementType X)
{   //在数组s中查找值为x的元素所属的集合
    //Maxsize是全局变量，为数组s的最大长度
    inti;
    for(i=0 ; i<MaxSize && S[i].Data!=X ; i++);
    if(i>=MaxSize)
    {return -1;} //未找到x，返回-1
    for(;S[i].Parent>=0;i=S[i].Parent);
    return i; //找到x所属集合,返回树根结点在数组s中的下标
}

集合的并运算

  • 查找两个元素所在的集合树的根结点
  • 如果两个节点不同根，则将其中一个根的parent设为另一个根的下标
void Union( SetType S[ ] , ElementType X1 , ElementType X2 )
{
    int Root1,Root2;
    Root1 = Find(S, X1);
    Root2 = Find(S, X2)
    if(Root1 != Root2)
    {S[Root2].Parent=Root1;}
}

  • 3的parent修改为下标0，即1
下标 Data parent
0 1 -1
1 2 0
2 3 0
3 4 0
4 5 2
5 6 -1
6 7 0
7 8 2
8 9 5
9 10 5

并查集合并的优化

  • 可以将根节点的parent改为表示集合元素个数
  • 在合并时将元素个数小的插入到元素个数大的集合中，可以控制树高