构建哈夫曼树并求解对应叶子节点对应的哈夫曼编码

C语言代码实现

#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);

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

    HuffmanCode HC;
    createHC(&HC,&HT,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("输出HT[%d]对应的哈夫曼编码：%s\n",i,HC[i]);
    }

}

void displayHT(HuffmanTree *HT,int n)
{
    int m=2*n-1;
    int i;
    for(i=1;i<=m;++i){
        printf("%d ",(*HT)[i].weight);
    }
    printf("\n");

}

运行结果：