首页 > 其他 > 详细

赫夫曼树

时间:2019-03-20 21:35:42      阅读:144      评论:0      收藏:0      [点我收藏+]

什么是赫夫曼树?

  赫夫曼树:树的带权路径长度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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!