欢迎来到天天文库
浏览记录
ID:20915423
大小:33.00 KB
页数:4页
时间:2018-10-17
《哈夫曼树 哈夫曼编码(先序遍历方法)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#include#includetypedefstructTree{intweight;intleft;intright;intparent;}*tree;voidCreateHuffman(intn){inti;intm1,m2,x1,x2;treeHuffman[100];for(i=0;i<2*n-1;i++){Huffman[i]=(tree)malloc(sizeof(structTree));}for(i=0;iweight);}for(i
2、=0;i<2*n-1;i++){Huffman[i]->parent=-1;Huffman[i]->left=-1;Huffman[i]->right=-1;}intj;for(i=0;iweightparent==-1){m1=Huffman[j]->weight;x1=j;}}for(j=0;jweight
3、parent==-1&&x1!=j){m2=Huffman[j]->weight;x2=j;}}Huffman[x1]->parent=n+i;Huffman[x2]->parent=n+i;Huffman[n+i]->weight=Huffman[x1]->weight+Huffman[x2]->weight;Huffman[n+i]->left=x1;Huffman[n+i]->right=x2;}for(i=0;i<2*n-1;i++){printf("%d,",Huffman[i]->weight);}printf("");for(i=0;
4、i<2*n-1;i++){printf("%d的左结点的下标为%d,右结点的下标为%d",Huffman[i]->weight,Huffman[i]->left,Huffman[i]->right);}chars[100];intx;i--;x=i;intk;k=0;intrs[100];intls[100];i=1;treeq[100];intsum=0;for(j=0;j<100;j++){rs[j]=0;ls[j]=0;s[j]=' ';}while(i!=0){if(i==1&&k==0){q[i]=Huffman[x];s[i-1]='
5、*';k++;}while(q[i]->left!=-1&&ls[i]==0){x=Huffman[x]->left;ls[i]=1;i++;k++;q[i]=Huffman[x];s[i-1]='0';ls[i]=0;rs[i]=0;}if((q[i]->left==-1&&q[i]->right!=-1&&rs[i]==0)
6、
7、(ls[i]==1&&q[i]->right!=-1&&rs[i]==0)){x=Huffman[x]->right;rs[i]=1;i++;k++;q[i]=Huffman[x];s[i-1]='1';ls[i]=0;rs
8、[i]=0;}if((q[i]->left==-1&&q[i]->right==-1)){printf("%d:",q[i]->weight);for(j=1;jweight*(i-1);}if((q[i]->left==-1&&rs[i]==1)
9、
10、(q[i]->left==-1&&q[i]->right==-1)
11、
12、(q[i]->right==-1&&ls[i]==1)
13、
14、(rs[i]==1&&ls[i]==1)){i--;k++;Huffman[x]
15、=q[i];}}printf("带权长度为%d",sum);}voidmain(){intnum;printf("输入叶子结点个数:");scanf("%d",&num);CreateHuffman(num);printf("");}
此文档下载收益归作者所有