赫夫曼树基本数据结构

自编头文件：

#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