赫夫曼树基本数据结构

自编头文件：

#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED

#include<limits.h>
#include<string.h>
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;

void Select(HuffmanTree t,int n,int *s1,int *s2)
{
    int m1=INT_MAX,m2=INT_MAX;
    int pos1=0,pos2=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i].parent==0)
        {
            if(t[i].weight<m1)
            {
                m2=m1;
                pos2=pos1;
                m1=t[i].weight;
                pos1=i;
            }
            else if(t[i].weight<m2)
            {
                m2=t[i].weight;
                pos2=i;
            }
        }
    }
    *s1=pos1,*s2=pos2;
    return;
}
void HuffmanCoding(HuffmanTree *ht,HuffmanCode *hc,int* w,int n)
{
    if(n<=1)return;
    int m=n*2-1;
    HuffmanTree HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
    HuffmanTree p=HT+1;
    int i;
    for(i=1;i<=n;++i,++p,++w)
    {
        //*p={*w,0,0,0};
        p->weight=*w;p->parent=0;
        p->lchild=p->rchild=0;
    }
    for(;i<=m;++i,++p)
    {
        //*p={0,0,0,0};
        p->weight=p->parent=0;
        p->lchild=p->rchild=0;
    }

    int s1,s2;
    for(i=n+1;i<=m;++i)
    {//构建赫夫曼树
        Select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    //分配n个字符编码的头指针数组
    HuffmanCode HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    char *cd=(char*)malloc(n*sizeof(char));//分配暂存编码的空间
    cd[n-1]='\0';//编码结束符
    for(i=1;i<=n;++i)
    {//逐个字符求赫夫曼编码
        int start=n-1;
        int c=i,f=HT[i].parent;
        for(;f!=0;c=f,f=HT[f].parent)
        {//从叶子到根逆向求编码
            if(HT[f].lchild==c)cd[--start]='0';
            else cd[--start]='1';
        }
        HC[i]=(char*)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);
    }
    free(cd);
    *ht=HT,*hc=HC;
    return;
}

#endif // HUFFMAN_H_INCLUDED

主函数：

#include <stdio.h>
#include <stdlib.h>
#include "Huffman.h"
void output(HuffmanTree HT,HuffmanCode HC,int n)
{
    for(int i=1;i<=n;i++)
    {
        printf("权值%d节点的赫夫曼编码:%s\n",HT[i].weight,HC[i]);
    }
    return;
}
int main()
{
    int n;
    printf("请输入节点个数:");
    scanf("%d",&n);
    int w[n];
    for(int i=0;i<n;i++)
    {
        printf("请出入第%d个节点的权值:",i+1);
        scanf("%d",&w[i]);
    }
    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(&HT,&HC,w,n);
    output(HT,HC,n);
    return 0;
}

输出样例：

请输入叶子节点的个数:4
请输入第1个节点的权值:2
请输入第2个节点的权值:3
请输入第3个节点的权值:6
请输入第4个节点的权值:8
权值2节点的赫夫曼编码:100
权值3节点的赫夫曼编码:101
权值6节点的赫夫曼编码:11
权值8节点的赫夫曼编码:0