huffman 树

 1 #include <stdio.h>
 2 #define n 4
 3 typedef struct  
 4 {
 5     int parent;
 6     int lchild,rchild;
 7     int weight;
 8     int flag;
 9 }Node;
10 
11 typedef struct 
12 {
13     char bit[n];
14     int start;
15     char ch;
16 }CodeNode;
17 
18 Node haffman[7];
19 CodeNode code[n];
20 
21 int select(int j)
22 {
23     int i,position;
24     int Min=100;
25     for (i=0;i<=j;i++)
26         if (haffman[i].weight<Min && haffman[i].flag==-1)
27         {
28             Min=haffman[i].weight;
29             position=i;
30         }
31     haffman[position].flag=1;
32     return position;
33 }
34 
35 void haffmanCode()
36 {
37     int i,j,p,k;
38     
39     for (i=0;i<n;i++)
40     {
41         printf("%d ",haffman[i].weight);
42         code[i].start=n-1;
43         j=i;
44         p=haffman[i].parent;
45         while (p!=-1)
46         {
47             if (haffman[p].lchild==j)
48                 code[i].bit[code[i].start]='0';   //左0右1;
49             else
50                 code[i].bit[code[i].start]='1';
51             code[i].start--;
52             j=p;
53             p=haffman[p].parent;
54         }
55         for(k=code[i].start+1 ;k<n ;k++)
56           printf("%c",code[i].bit[k]);
57         printf("\n");
58     }
59 
60 }
61 
62 int main()
63 {
64     
65     int max=100 , i ;
66     int m1,m2;
67 
68     //初始化节点数据;
69     for (i=0;i<2*n-1;i++)
70     {
71         haffman[i].weight=0;
72         haffman[i].parent=-1;
73         haffman[i].lchild=-1;
74         haffman[i].rchild=-1;
75         haffman[i].flag=-1;
76     }
77     printf("请输入叶子节点的权值：");
78     for (i=0;i<n;i++)
79     {
80         scanf("%d",&haffman[i].weight);   
81     }
82     //构造哈弗曼二叉树（n-1次合并）;
83     for (i=n ; i<2*n-1 ;i++)
84     {
85         m1=select(i-1);        //最小权值位;
86         m2=select(i-1);     //次最小权值;
87         haffman[m1].parent=i;
88         haffman[m2].parent=i;  //父节点在数组中的位置;
89         haffman[i].weight=haffman[m1].weight+haffman[m2].weight;
90         haffman[i].lchild=m1;
91         haffman[i].rchild=m2;    //儿子节点在数组中的位置;
92         
93     }
94     for (i=0 ;i<2*n-1 ;i++)
95         printf("%d",haffman[i].weight);
96     printf("\n");
97     haffmanCode();
98 }