什么是赫夫曼树?
赫夫曼树:树的带权路径长度WPL最小的二叉树,又称最优二叉树。
1 void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) 2 { 3 int i=0,s1=0,s2=0,c=0,start=0,f=0; 4 if(n <=1 ) return; 5 int m=2*n-1; 6 char *cd; 7 HuffmanTree p; 8 *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 9 for(p=*HT+1,i=1;i<=n;++i,++p,++w){ 10 p->weight=*w; 11 p->parent=0; 12 p->lchild=0; 13 p->rchild=0; 14 } 15 for(;i<=m;++i,++p){ 16 p->weight=0; 17 p->parent=0; 18 p->lchild=0; 19 p->rchild=0; 20 } 21 for(i=n+1;i<=m;++i){ 22 Select(HT,i-1,&s1,&s2); //选择parent为0,且weight最小的两个结点,序号分别为s1,s2 23 printf("s1: %d, s2: %d\n",s1,s2); 24 (*HT)[s1].parent=i; 25 (*HT)[s2].parent=i; 26 (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; 27 (*HT)[i].lchild=s1; 28 (*HT)[i].rchild=s2; 29 } 30 *HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); 31 cd=(char *)malloc(n*sizeof(char)); 32 cd[n-1]=‘\0‘; 33 for(i=1;i<=n;++i){ 34 start=n-1; 35 for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent){ 36 if((*HT)[f].lchild == c){ 37 cd[--start]=‘0‘; 38 }else{ 39 cd[--start]=‘1‘; 40 } 41 } 42 (*HC)[i]=(char *)malloc((n-start)*sizeof(char)); 43 strcpy((*HC)[i],&cd[start]); 44 } 45 free(cd); 46 }
原文:https://www.cnblogs.com/ciel12138/p/10567832.html