关于中序遍历HuffmanTree的问题

xiaxueyi

原帖由 holyzfy 于 2007-5-31 13:15 发表
InOrderTraverse(HT2+HT->lchild,HT2); //什么意思啊？

[code]
/*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
void InOrderTraverse(HuffmanTree HT,Huf ...

我估计，程序用的是一个结构体数组来存储树的信息，HT2是该数组的首地址，HT是当前节点的结构体地址，lchild和rchild都是左右孩子结构体在该数组中的索引，大体上可以解释通  

holyzfy

1. 
   
2. /****************************************************************************
   
3. 文件名：Huffman.cpp
   
4. 修改历史：
   
5.          1.函数Output(HT,HC,n)的输出表示增加了制表位
   
6.          2.修改Select(HuffmanTree &HT,int i,int &s1,int &s2),
   
7.            具体为:for(j = 1; j <= i; j++)之处为把j<i改成j<=i
   
8. 尚存在的问题：中序遍历？？
   
9. 最后修改日期：2007,5,30
   
10. *****************************************************************************/
    
11. #include <stdlib.h>
    
12. #include <iostream.h>
    
13. #include <string.h>
    
14. 
    
15. #define MAX_SIZE 50
    
16. #define  OVERFLOW -1
    
17. 
    
18. typedef struct
    
19. {  
    
20.         char letter;
    
21.         int weight;
    
22.         int parent;
    
23.         int lchild;
    
24.         int rchild;
    
25. }HTNode,*HuffmanTree;
    
26. 
    
27. typedef char * *HuffmanCode;
    
28. 
    
29. /***************************************************************************
    
30. 函数名称：void Select(HuffmanTree &HT,int i,int &s1,int &s2)
    
31. 功能描述：在HT[1...i]选择parent为空且weight最小的两个结点，其下标分别为s1,s2
    
32. 具体实现：先把输入的第一个字符的权值的下标赋给s1，然后把每个字符的权值与 HT[s1].weight比较，
    
33.           直至遍历输入的所有字符，把权值最小的下标赋给s1；用同样的方法再找到s2
    
34. ****************************************************************************/
    
35. void Select(HuffmanTree &HT,int i,int &s1,int &s2)
    
36. {
    
37.         int j, k;
    
38. 
    
39.         for(k = 1; k < i; k++)
    
40.         {
    
41.                 if(HT[k].parent != NULL)
    
42.                         continue;
    
43.                 s1 = k; //初始化s1
    
44.                 break;
    
45.         }
    
46. 
    
47.         for(j = 1; j <= i; j++)
    
48.         {
    
49.                 if(HT[j].parent != NULL)
    
50.                         continue;
    
51.                 if(HT[j].weight < HT[s1].weight)
    
52.                         s1 = j;
    
53.         }
    
54. 
    
55.         for(k = 1; k <= i; k++)
    
56.         {
    
57.                 if(HT[k].parent != NULL || k == s1)
    
58.                         continue;
    
59.                 s2 = k;
    
60.                 break;
    
61.         }
    
62.        
    
63.         for(j = 1; j <= i; j++)
    
64.         {
    
65.                 if(HT[j].parent != NULL)
    
66.                         continue;
    
67.                 if(HT[j].weight <= HT[s2].weight && j != s1)
    
68.                         s2 = j;
    
69.         }
    
70.        
    
71. } //end of void Select(HuffmanTree &HT,int i,int &s1,int &s2)
    
72. 
    
73. 
    
74. /*根据输入的字符及其权值建立哈夫曼树*/
    
75. void Creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,char *zifu,int *w,int n)
    
76. {
    
77.         HuffmanTree p;
    
78.         int m,s1,s2;
    
79.         for(int i=0;i<n;i++) //输入字符
    
80.         {
    
81.                 cout<<"请输入第"<<i+1<<"个字符:";
    
82.                 cin>>zifu[i];
    
83.         }
    
84. 
    
85.         for(i=0;i<n;i++) //输入字符对应的权值
    
86.         {
    
87.                 cout<<"请输入字符"<<zifu[i]<<"的权值:";
    
88.                 cin>>w[i];
    
89.         }
    
90.        
    
91.         if(n <= 1)
    
92.                 return;
    
93.         m = 2*n-1;
    
94.         if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))
    
95.                 exit(OVERFLOW);
    
96.         for(p=HT+1,i=1;i<=n;++i,++zifu,++p,++w)
    
97.         {
    
98.                 /*生成独立的森林*/
    
99.                 p->parent = NULL;
    
100.                 p->letter = *zifu;
     
101.                 p->lchild = NULL;
     
102.                 p->rchild = NULL;
     
103.                 p->weight = *w;
     
104.         }
     
105.        
     
106.         for(;i<=m;++i,++p)
     
107.         {
     
108.                 (*p).weight=0;
     
109.                 (*p).parent=0;
     
110.                 (*p).lchild=0;
     
111.                 (*p).rchild=0;
     
112.         }
     
113.        
     
114.         for(i=n+1;i<=m;++i)
     
115.         {
     
116.                 Select(HT,i-1,s1,s2);
     
117.                 HT[s1].parent=i;
     
118.                 HT[s2].parent=i;
     
119.                 HT[i].lchild=s1;
     
120.                 HT[i].rchild=s2;
     
121.                 HT[i].weight=HT[s1].weight+HT[s2].weight;
     
122.         }
     
123. }
     
124. 
     
125. /*从叶子到根求每个字符的编码*/
     
126. void  HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zifu,int *w,int n)
     
127. {
     
128.     int c,f;
     
129.         char *cd;
     
130.         int start = 1;
     
131.         HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
     
132.         cd=(char*)malloc(n*sizeof(char));/*临时的code存储*/
     
133.         cd[n-1]='\0'; //编码结束符
     
134. 
     
135.         for(int i=1;i<=n;++i)
     
136.         {
     
137.                 start = n - 1; //编码结束符位置
     
138. 
     
139.         //从叶子到根逆向求编码
     
140.                 for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
     
141.                         if(HT[f].lchild == c)
     
142.                                 cd[--start] = '0'; //树中的左分支表示字符'0'
     
143.                         else
     
144.                                 cd[--start] = '1'; //树中的右分支表示字符'1'
     
145.                         HC[i] = (char *)malloc((n - start) * sizeof(char));
     
146.                         strcpy(HC[i], &cd[start]);        //从cd复制编码（串）到HC       
     
147.         }
     
148.         free(cd);
     
149. }
     
150. 
     
151. /*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
     
152. void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2)
     
153. {
     
154.         if(HT->lchild!=0)
     
155.                 InOrderTraverse(HT2+HT->lchild,HT2);
     
156.         {//如果某个结点有孩子，显然它是内结点，应将其标记出来
     
157.                 if(HT->lchild!=0)
     
158.                         cout<<","<<HT->weight<<"(内点)";
     
159.                 else
     
160.                         cout<<","<<HT->weight;
     
161.         }
     
162.         if(HT->rchild!=0)
     
163.                 InOrderTraverse(HT2+HT->rchild,HT2);
     
164. } //end of void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2,int n)
     
165. 
     
166. /*输出各字符的哈夫曼编码*/
     
167. void Output_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int n)
     
168. {
     
169.         cout<<"\nchar"<<"\tweight"<<"\thuffmancode\n";
     
170.     for(int i=1;i<=n;i++)
     
171.         cout<<HT[i].letter<<"\t"<<HT[i].weight<<"\t"<<HC[i]<<endl;
     
172. } //end of void Output_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int n)
     
173. 
     
174. void main()
     
175. {
     
176.         HuffmanTree HT;
     
177.         HuffmanCode HC;
     
178.         int i=0;
     
179.         char zifu[MAX_SIZE]; //zifu[]为存放字符的数组
     
180.         int n=0,w[MAX_SIZE]; //w[]为存放权值的数组
     
181.         cout<<"请输入字符的个数:";
     
182.         cin>>n;
     
183.         if(n<=0 || n>MAX_SIZE)
     
184.         {
     
185.                 cerr<<"字符个数必须为不大于50的自然数!\n";
     
186.                 exit(1);
     
187.         }
     
188.     Creat_HuffmanTree(HT,HC,zifu,w,n);
     
189.         HuffmanCoding(HT,HC,zifu,w,n);
     
190.     Output_HuffmanTree(HT,HC,n);
     
191. 
     
192.         {//这个花括号内的功能为中序遍历HuffmanTree
     
193.     while(HT[i].parent!=0) i++; //确定HuffmanTree的所有结点数i
     
194.     cout<<"\n中序遍历HuffmanTree结果如下:\n";
     
195.         InOrderTraverse(HT+i,HT);
     
196.         cout<<endl;
     
197.         }
     
198. } //end of void main()
     

复制代码

[ 本帖最后由 holyzfy 于 2007-5-31 21:11 编辑 ]

lenovo

原帖由 holyzfy 于 2007-5-31 18:56 发表
[code]
/****************************************************************************
文件名：Huffman.cpp
修改历史：
         1.函数Output(HT,HC,n)的输出表示增加了制表位
         2.修改Select(H ...

先去吃饭，有时间帮你看看。

ailantian

我来回复一下，如果不对的话，大家包含
楼主参数没给清楚，让大家猜，就像话说半句，让别人看什么意思。难为人了。
有参数来看
比如我们分析一种最简单的情况，假设左节点一直有，这个程序的过程应当如下
遍历的节点为A，B，C，D，E，F........等等
则其第一个参数的分析如下，HT2因为是一个地址，所以我们可以当一个常数来看待,假定是0x80000000
，至于最开始的地址，我们当根节点
A(HT,HT2)                    即判断根节点的左儿子的权值
B(HT2+HT->lchild,HT2)即HT2的地址，加上根节点的左儿子的权值
C(HT2+B->lchild,HT2) 即HT2的地址，加上B节点的左儿子的权值
D(HT2+C->lchild,HT2) 即HT2的地址，加上C节点的左儿子的权值
E(HT2+D->lchild,HT2)
F(HT2+E->lchild,HT2)


内存结构示意图大致如下
至于内存为什么不重复，这个可能和生成树的时候的约定有关。
主意遍历的顺序是走 根->A->B->C->D.....

[ 本帖最后由 ailantian 于 2007-5-31 21:09 编辑 ]

ailantian

晕，只看了第一贴，没看到后面：）

holyzfy

终于联系到写这段程序的本人了，呵呵，还是个女的~，她说的意思是HT2+HT->lchild可以看成是HT2[HT->lchild]，这样就好理解了，可是改后并不能直接用，编译器提示“ error C2664: 'InOrderTraverse' : cannot convert parameter 1 from 'HTNode' to 'HTNode *'”，这个错误好改，取地址就行了，
附上改后的程序

1. 
   
2. /*中序遍历HuffmanTree,输出其结点值,并对内部结点作标记*/
   
3. void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2)
   
4. {
   
5.         if(HT->lchild!=0)
   
6.                 InOrderTraverse(HT2[HT->lchild],HT2);
   
7.         {//如果某个结点有孩子，显然它是内结点，应将其标记出来
   
8.                 if(HT->lchild!=0)
   
9.                         cout<<","<<HT->weight<<"(内点)";
   
10.                 else
    
11.                         cout<<","<<HT->weight;
    
12.         }
    
13.         if(HT->rchild!=0)
    
14.                 InOrderTraverse(&HT2[HT->rchild],HT2);
    
15. } //end of void InOrderTraverse(HuffmanTree HT,HuffmanTree HT2,int n)
    

复制代码

lenovo

原帖由 holyzfy 于 2007-5-31 22:07 发表
终于联系到写这段程序的本人了，呵呵，还是个女的~，她说的意思是HT2+HT->lchild可以看成是HT2[HT->lchild]，这样就好理解了，可是改后并不能直接用，编译器提示“ error C2664: 'InOr ...

明白就好。
给你4个字母，
分别是a，b，c，d，
权重分别为3，4，5，6。
程序的输出是多少？

holyzfy

不介意被你考，毕竟才学数据结构

char    weight  huffmancode
a       3       00
b       4       01
c       5       10
d       6       11

中序遍历HuffmanTree结果如下:
,3,7(内点),4,18(内点),5,11(内点),6

ailantian

我觉得她的那个代码写的比较晦涩，
我想如果是我写，我可能应该是用指针，而不是用整形来表示那个地址。虽然可以用，
但是程序不好理解。

lenovo

原帖由 ailantian 于 2007-6-1 09:08 发表
我觉得她的那个代码写的比较晦涩，
我想如果是我写，我可能应该是用指针，而不是用整形来表示那个地址。虽然可以用，
但是程序不好理解。

用整数就是为了避免使用指针。
我觉得理解起来不算难吧，
如果你学过数据结构。