哈夫曼树

1. 相关概念:

1. 结点的路径长度

定义: 从根结点到该结点的连接数

2. 树的路径长度

定义: 所有叶结点的路径长度之和

3. 结点的权

梗概: 根据实际问题需要, 每个结点都有一个实数, 作为该结点的权值

4. 结点的带权路径长度

定义: 结点的路径长度×该结点的权

5. 树的带权路径长度(WPL)

定于: 树中所有叶结点的带权路径长度之和

2. 哈夫曼树定义:

1. 梗概:

哈夫曼树是一种特殊二叉树

1. 哈夫曼树的每个结点都储存有权重
   1. 由实际问题得到每个每个叶结点的权重, 双亲结点的权重由两个孩子结点得到
2. 给定n个带权叶子结点, 其构造的所有二叉树中, 哈夫曼树的带权路径长度最小
3. 哈夫曼树结点不存储数据, 用权来映射/代表数据

2. 哈夫曼树的结构:

每个结点有四个部分:

1. 权值域
   1. 存储权值
2. 双亲域(根结点域)
   1. 存储双亲位置
3. 左孩子域
   1. 存储左孩子位置
4. 右孩子域
   1. 村粗右孩子位置

3. 哈夫曼树性质:

1. 结点总数=2×叶子结点数-1
   1. 直观理解:
      1. 

4. 操作:

1. 构造哈夫曼树

梗概

• 是一个贪婪算法
• 每次都选取最小的两个节点形成父节点

步骤

1. 给定n个具有权值的独立结点
2. 选出权值最小的两个结点(从剩余叶结点和根结点中选), 构成一颗树
   1. 权值小的作为左孩子
   2. 构造一个新的结点A, 作为这两个结点的根结点, 并给该根结点赋予权值
      1. 该根结点的权值=左右孩子的权值之和
3. 重复以上步骤, 直到所有独立结点都归并到哈夫曼树中

5. 在C语言中的实现:

1. 梗概:

1.1. 结构定义:

1. 哈夫曼树的结点采用数组来存储
2. 结点间的位置用数组下标表示
3. 数组0下标不存储结点, 用来表示空结点
4. 为方便使用, 1n下标存放叶结点, n+12n-1存放双亲结点

1.2. 构造哈夫曼树

分两大步:

1. 初始化哈夫曼树的结点容器
   1. 每个结点的各个域都赋值为0
2. 根据权重确定哈夫曼树的结点位置
   1. 其中每次都在选剩的叶结点和构造的根结点中选最小的两个
      1. 因为双亲结点就是权最小的两结点的其中一个

2. 代码的性质

1. 某个权值的结点在哈夫曼树位置=对应权值在权值数组位置+1
   1. 因为哈夫曼树的数组中第0个元素不使用

3. 代码实现:

3.1. 哈夫曼树定义:

#define N 64  //叶子结点数的最大值,可修改
#define M 2*N-1 //总结点数的最大值,不可修改
typedef WeightType int
typedef struct {
    WeightType weight;
    int parent;
    int LChild, RChild;
}HTNode, HuffmanTree[M+1];

3.2. 按值查找

int HTLocate(HuffmanTree ht,WeightType w,int n){
    for (int i=1;i<=n;++i)
        if(ht[i].weight==w)
            return i;
}

3.3. 构造哈夫曼树

void CrtHuffmanTree (HuffmanTree ht, int w[],int n){
    //ht为哈夫曼树数组空间,w[]为所需权重集合,n为权重个数    
    void select(HuffmanTree ht,int end,int *s1,int *s2){
		//在ht数组中选权值最小的两个,较小的赋给s1,较大的赋给s2
        int j,min1=36767,min2=32767;
        for(j=1;j<=end;++j){
            /*只有parent为0才能在其上构造双亲结点*/
            if((ht[j].parent==0)&&(ht[j].weight<min2)){
                if(ht[j].weight<min1){
                    min2=min1;
                    *s2=*s1;
                    min1=ht[j].weight;
                    *s1=j;
                }
                else {
                    min2=ht[j].weight;
                    *s2=j;
                }
            }
        }
    }
    /*叶结点初始化*/
    int i,m,s1,s2;
    for (i=1;i<=n;i++){
        ht[i].weight=w[i-1];
        ht[i].parent=ht[i].LChild=ht[i].RChild=0;
    }
    /*双亲结点初始化*/
    m= 2*n-1;
    for(i=n+1;i<m;i++){
        ht[i].weight=ht[i].parent=ht[i].LChild=ht[i].RChild=0;
    }
    /*根据权重确定位置关系*/
    /*这里i指向刚构造的双亲结点*/
    for(i=n+1;i<=m;i++){
        /*在剩余叶结点和刚构造的根结点中选
        最小的两个,分别赋给s1和s2*/
        select(ht,i-1,&s1,&s2);
        /*关系确立*/
        ht[i].weight=ht[s1].weight+ht[s2].weight;
        ht[s1].parent=i; ht[s2].parent=i;
        ht[i].LChild=s1; ht[i].RChild=s2;
    }
}

6. 哈夫曼树的应用:

1. 哈夫曼编码

child::哈夫曼编码