使用C语言编程实现哈夫曼树的构造，以及对该赫夫曼树的编码

哈夫曼树的构造：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define MAXBIT 20
#define INFINITY 32767

typedef struct
{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void CreateHuffmanTree(HuffmanTree *HT,int n)
{
    if(n<=1) return;
    int m=2*n-1;
    *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    HuffmanTree p=*HT;
    for(int i=1;i<=n;i++,p++)
    {
        scanf("%d",&(p->weight));
        p->parent=p->lchild=p->rchild=0;
    }
    for(int i=n+1;i<=m;i++,p++)
    {
        p->weight=p->parent=p->lchild=p->rchild=0;
    }
    for(int i=n+1;i<=m;i++)
    {
        int s1=0,s2=0;
        int w1=INFINITY,w2=INFINITY;
        for(int j=1;j<i;j++)
        {
            if((*HT)[j].parent==0)
            {
                if((*HT)[j].weight<w1)
                {
                    w2=w1;
                    s2=s1;
                    w1=(*HT)[j].weight;
                    s1=j;
                }
                else if((*HT)[j].weight<w2)
                {
                    w2=(*HT)[j].weight;
                    s2=j;
                }
            }
        }
        (*HT)[s1].parent=i;
        (*HT)[s2].parent=i;
        (*HT)[i].lchild=s1;
        (*HT)[i].rchild=s2;
        (*HT)[i].weight=w1+w2;
    }
}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int n)
{
    *HC=(char**)malloc((n+1)*sizeof(char*));
    char *cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(int i=1;i<=n;i++)
    {
        int start=n-1;
        int c=i,f=(*HT)[i].parent;
        while(f!=0)
        {
            if((*HT)[f].lchild==c) cd[--start]='0';
            else cd[--start]='1';
            c=f;
            f=(*HT)[f].parent;
        }
        (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i],&cd[start]);
    }
    free(cd);
}

int main()
{
    HuffmanTree HT;
    HuffmanCode HC=NULL;
    int n;
    scanf("%d",&n);
    CreateHuffmanTree(&HT,n);
    HuffmanCoding(&HT,&HC,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d %s\n",HT[i].weight,HC[i]);
    }
    return 0;
}

输入格式为：第一行输入叶子结点的个数 n，第二行输入 n 个整数，表示每个叶节点的权重。

输出格式为：每行输出一个叶节点的权重和对应的哈夫曼编码。

代码思路：

1. 构造哈夫曼树

2. 哈夫曼编码

具体实现细节见代码注释。