哈夫曼树与哈夫曼编码

---

1. 哈夫曼树
   哈夫曼树又称最优二叉树，是一种带权路径最短的二叉树。
   对于给定的n个叶子结点，在构建哈夫曼树时只需要遵循一个原则：结点权重越大的离根结点越近。
   哈夫曼算法流程简述如下：
   1）在给定的n个叶结点中选择两个权值最小的两个结点，作为左右子树构建一棵新的二叉树，并且设置新的二叉树的根节点权值为左右子树上根节点的权值和；
   2）在原有的n个结点中删除那两个权值最小的两个节点，并将新的二叉树根节点加入；
   3）重复1、2两步，直到所有的结点构建成了一棵二叉树为止，这棵二叉树即使哈夫曼树。

2. 哈夫曼编码
   哈夫曼编码是一种最短的二进制前缀编码。对于给定的n个字符，要构建其对应的二进制前缀编码，并使得所有字符的编码长度之和最小，可以通过构建这n个字符对应的哈夫曼树来实现，每个字符对应权重就是其自身出现的频率，使用频率高的权重也高；哈夫曼树的n个叶子节点就是对应的n个字符，所以求每个字符的编码时就是从该字符对应的叶结点走一条到根节点的路劲。

---

哈夫曼树和哈夫曼编码的构建代码如下：

#include<stdio.h>
#include<stdlib.h>

//定义静态三叉链表的结构体
typedef struct HuffmanTree{
    int weight; //节点权重
    int parent; //父节点在数组中的下标
    int lchild; //左孩子在数组中的下标
    int rchild; //右孩子在数组中的下标
}Hnode,*HuffmanTree;

typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码

void createHT(HuffmanTree *HT,int w[],int n);
void select(HuffmanTree *HT,int n,int *s1,int *s2);
void displayHT(HuffmanTree HT,int n);
void createHC(HuffmanCode **HC,HuffmanTree *HT,int n);
void displayHC(HuffmanCode *HC,int w[],int n);

int main(int argc,char **argv)
{
    HuffmanTree HT;
    int n=8;
    int w[]={7,19,2,6,32,3,21,10}; //n个叶子节点对应的权重
    int s1;
    int s2;
    createHT(&HT,w,n);
    printf("哈夫曼树中所有节点的信息:\n");
    displayHT(HT,n);

    HuffmanCode* HC;
    createHC(&HC,&HT,n);
    displayHC(HC,w,n);


    return 0;
}

//创建哈夫曼树
//HT为地址传递的存储哈夫曼树的数组，w为存储叶子节点权重的数组，n为叶子节点的数量
void createHT(HuffmanTree *HT,int w[],int n)
{
    //包含n个叶子节点的哈夫曼树共有2n-1个节点
    int m=2*n-1;
    //申请哈夫曼树需要的空间，包含头节点
    (*HT)=(Hnode*)malloc((m+1)*sizeof(Hnode));
    //初始化树的叶子节点
    int i;
    for(i=1;i<=n;++i){
        (*HT)[i].weight=w[i-1];
        (*HT)[i].parent=0;
        (*HT)[i].lchild=0;
        (*HT)[i].rchild=0;
    }
    //初始化非叶子节点
    for(i=n+1;i<=m;++i){
        (*HT)[i].weight=0;
        (*HT)[i].parent=0;
        (*HT)[i].lchild=0;
        (*HT)[i].rchild=0;
    }

    int s1;
    int s2;
    //更新非叶子节点的权重，以及树中各节点的双亲和孩子指针指向
    for(i=n+1;i<=m;++i){
        //筛选权重最小且parent指针为空的两个节点，并将节点的序号赋值给s1,s2；
        select(HT,i-1,&s1,&s2);
        (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
        (*HT)[i].lchild=s1;
        (*HT)[i].rchild=s2;
        (*HT)[s1].parent=i;
        (*HT)[s2].parent=i;
    }
}

//筛选权重最小且parent指针为空的两个节点
/*s1,s2传入的是实参的地址，函数运行完成后，实参中存放的
自然就是哈夫曼树中权重最小的两个节点在数组中的位置。
*/
void select(HuffmanTree *HT,int n,int *s1,int *s2)
{
    int i=1;
    //找到还没有构建树的节点
    while(i<=n && (*HT)[i].parent!=0){
        ++i;
    }
    *s1=i;
    int min;
    min=(*HT)[i].weight;
    ++i;
    while(i<=n && (*HT)[i].parent!=0){
        ++i;
    }
    //对找到的两个节点比较大小，*s1始终指向权重较小的那个节点
    if((*HT)[i].weight<min){
        *s2=*s1;
        *s1=i;
    }
    else{
        *s2=i;
    }
    //两个节点和后续所有未构建树的节点进行比较
    int j;
    for(j=i+1;j<=n;++j){
        //如果有父节点，直接跳过，进行下一个
        if((*HT)[j].parent!=0){
            continue;
        }
        //如果比最小的还小，更新*s1,*s2两个的指向
        if((*HT)[j].weight<=(*HT)[*s1].weight){
            *s2=*s1;
            *s1=j;
        }
        //如果介于两个之间，更新*s2的指向
        else if((*HT)[j].weight<(*HT)[*s2].weight){
            *s2=j;
        }
    }
}

//求叶子节点对应的哈夫曼编码
/*
哈夫曼树构建完毕，从n个叶子节点到根，逆向求叶子节点对应的哈夫曼编码
HC为地址传递的存储叶子节点对应哈夫曼编码的字符数组
*/
void createHC(HuffmanCode **HC,HuffmanTree *HT,int n)
{
    //分配n个叶子节点对应哈夫曼编码的头指针
    *HC=(HuffmanCode*)malloc((n+1)*sizeof(char*));
    //申请求当前叶子节点编码的辅助空间
    char *cd=(char*)malloc(n*sizeof(char));
    //编码是从叶子节点往根节点逆向求解的，因此存储时需从右往左逐位存放编码
    //注意C语言中逐个字符地给字符数组赋值并不会自动添加'\0'，只有由""包围的字符串会自动在末尾添加'\0'.
    //首先存放编码结束符
    cd[n-1]='\0';
    int i;
    int start;
    int h;
    int p;
    for(i=1;i<=n;++i){
        //初始化编码起始指针
        start=n-1;
        //从叶子到根求编码
        for(h=i,p=(*HT)[i].parent;p!=0;h=p,p=(*HT)[p].parent){
            if((*HT)[p].lchild==h){
                cd[--start]='0'; //左分支标记为0；
            }
            else{
                cd[--start]='1'; //右分支标记为1；
            }
        }
        //为第i个编码分配存储空间，注意分配的存储空间的大小
        (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i],&cd[start]);
       // printf("输出权重为%d的叶结点对应的哈夫曼编码：%s\n",(*HT)[i].weight,(*HC)[i]);
    }
    free(cd); //释放工作区间
}

//打印哈夫曼树中所有结点的权重
void displayHT(HuffmanTree HT,int n)
{
    int m=2*n-1;
    int i;
    printf("weight parent lchild rchild\n");
    for(i=1;i<=m;++i){
        printf("%3d %6d %6d %6d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    }
    printf("\n");
}

//打印对应权重叶结点的哈夫曼编码
void displayHC(HuffmanCode *HC,int w[],int n)
{
    int i;
    for(i=1;i<=n;++i){
        printf("权重为%d的叶结点对应的哈夫曼编码为：%s\n",w[i-1],HC[i]);
    }
}

运行结果：

运行结果