哈夫曼树

数据结构速通之哈夫曼树

前导概念

1.节点的路径长度：从根节点到该节点路径上经过的节点数
2.树的路径长度：某树所有叶节点的路径长度之和
3.结点的带权路径长度：结点的路径长度与结点权值之积
权值：在实际应用场景中赋予每个节点的属性
4.树的带权路径长度WPL：树的所有叶结点的带权路径长度之和
==哈夫曼树：WPL最小的二叉树==

哈夫曼树的构造

1.给出初始森林，其中每个树均只有一个结点，每个节点均有所对应的权值。
2.循环：合并两棵权值最小的二叉树（引入一个权值为该两棵二叉树权值之和的节点，将这两棵二叉树作为其子树，该树的权值即为根节点的权值），直到森林中只有一棵树。

应用场景：哈夫曼编码

知乎链接
哈夫曼编码是一种对文本存储进行压缩的==不定长编码方式==。
为了解决不定长编码所带来的多义性所创造的最优编码算法。
原理以后再补

实操

相关题目
洛谷 P2168荷马史诗
AcWing 3531

节点类型

typedef struct HNode{
    int weight;
    struct HNode *lc;
    struct HNode *rc;
}*Htree;

哈夫曼树的构建

Htree createHtree(int arr[],int n)
{
    Htree forest[N];
    Htree root=NULL;
    int minn,minnSub;
    for(int i=0;i<n;i++)//创建初始森林
    {
        Htree temp;
        temp= (Htree)malloc(sizeof(struct HNode));
        
        temp->lc=temp->rc=NULL;
        temp->weight=arr[i];
        forest[i]=temp;
    }
    for(int i=0;i<n-1;i++)//n-1次合并
    {
        minn=-1,minnSub=-1;
        //-----------初始化min与minnSub
        for (int j = 0; j < n; j++)
        {
            if(forest[j]!=NULL&&minn==-1)
            {
                minn=j;
                continue;
            }
            if(forest[j]!=NULL)
            {
                minnSub=j;
                break;
            }
        }
        //-----------------
        for(int j=minnSub;j<n;j++)
        {
            if(forest[j]!=NULL)
            {
                if(forest[j]->weight<forest[minn]->weight)
                {
                    minnSub=minn;
                    minn=j;
                }
                else if(forest[j]->weight<forest[minnSub]->weight)
                {
                    minnSub=j;
                }
            }
        }
        Htree root=(Htree)malloc(sizeof(struct HNode));
        root->weight=forest[minn]->weight+forest[minnSub]->weight;
        root->lc=forest[minn];
        root->rc=forest[minnSub];
        forest[minn]=root;
        forest[minnSub]=NULL;
    }
    return root;
}

计算哈夫曼树的WPL(递归)

//求哈夫曼树的WPL
int getWPL(Htree t,int n){
    if(t==NULL){
        return 0;
    }
    else if(!(t->lc||t->rc)){
        return n*t->weight;
    }
    else{
        return getWPL(t->lc,n+1)+getWPL(t->rc,n+1);
    }
}

计算哈夫曼编码

//计算哈夫曼编码
void hcode(Htree t,int len,int arr[]){
    if(t!=NULL){
        if(!(t->lc||t->rc)){
            printf("Node:%d:",t->weight);
            for(int i=0;i<len;i++){
                printf("%d",arr[i]);
            }
            printf("\n");
        }
        else{
            arr[len]=0;
            hcode(t->lc,len+1,arr);
            arr[len]=1;
            hcode(t->rc,len+1,arr);
        }
    }
}