现在介绍数据结构中的树，由于不像链表、队列、栈一样可以直接的线性化地理解，树在一定程度上给予我们较大的理解问题。由间及难，一般大多开始研究二叉树。
先附上最近的数据结构作业——Huffman编码，提供实例参考和理解。
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 6 using namespace std; 7 8 typedef struct{ 9 //char data; 10 int weight; 11 int lchild,rchild,parent; 12 }HTNode,*HuffmanTree; 13 14 typedef char **HuffmanCode; 15 16 void menu(){ 17 cout<<"-------------------------------------------------------------------------"<<endl; 18 cout<<"菜单：输入0-6实现以下操作"<<endl; 19 cout<<"0：结束实验！"<<endl; 20 cout<<"1：实现对给定源文件的电文字符统计操作！"<<endl; 21 cout<<"2：根据统计字符结果建立Huffman树！"<<endl; 22 cout<<"3：根据提供正文内容和已经建立好的Huffman树对正文不同字符进行Huffman编码!"<<endl; 23 cout<<"4: 实现BuildCodeFiles函数，将正文内容以Huffman编码生成01代码文件!"<<endl; 24 cout<<"5: 用Huffman编码对给定译文文件进行译码!"<<endl; 25 cout<<"-------------------------------------------------------------------------"<<endl; 26 27 } 28 int Count(char *text,int *w){/**Count返回字符个数，char[]存不同字符，体现种类，w[]存相应的权值**/ 29 30 int s=0,i; 31 char ch; 32 char filename[20];/**？：next[]、w[]动态开数组，对于同一个头地址，后续一个一个添加元素**/ 33 FILE *fp; 34 cout<<"实现电文字符数据统计，输入源文件名："<<endl; 35 cin>>filename; 36 getchar(); 37 38 while((fp=fopen(filename,"r"))==NULL){ 39 cout<<"无法打开文件！重新输入文件名："<<endl; 40 cin>>filename; 41 getchar(); 42 } 43 ch=getc(fp);/**问？：fp指针的指向，外层循环先getc，s值正常；若在循环内第一句作为getc开始，ch会在最后在读取一个空字符**/ 44 while(feof(fp)==0){ 45 //ch=getc(fp); 46 if(s==0){ /**第一个字符**/ 47 text[s]=ch; 48 w[s]++; 49 //cout<<text[s]<<w[s]<<endl; 50 s++;/**s超前一位；由于树结构不用0号位而text[]w[]都用0号位，相应赋值的数组下标关系需要注意**/ 51 ch=getc(fp); 52 continue; 53 } 54 for(i=0;i<s;i++){/**每读取成功一个，存入后s++，此处单次循环范围也随之增加*/ 55 if(ch==text[i]){/**若在已存储的text[]中找到 则对应位置权值数组元素++*/ 56 w[i]++; 57 //cout<<text[i]<<w[i]<<endl; 58 break; 59 } 60 } 61 if(i==s){/**未找到，先利用i=S存入，再自加，因为跳出for循环时，i已经++*/ 62 text[i]=ch; 63 w[i]++; 64 //cout<<text[i]<<w[i]<<endl; 65 s++; 66 } 67 ch=getc(fp); 68 } 69 70 fclose(fp); 71 return s;/**?:s-1 **/ 72 } 73 74 void Select(HuffmanTree &HT,int i,int &s1,int &s2){/**选择指定范围内的权值最小的两个结点*/ 75 int j,k; 76 int min1; 77 int min2; 78 for(k=1;k<=i;k++){/**找到每构造一次新的结点时的初态，即最前面的parent=0的结点*/ 79 if(HT[k].parent==0){ 80 j=k; 81 min1=k; 82 min2=k; 83 break; 84 } 85 } 86 for(j=k+1;j<=i;j++){/**min1,min2找法不同*/ 87 if(HT[j].parent==0){ 88 if(HT[j].weight<HT[min1].weight){/**min1:先定最前无双亲为最小，向后推一个再找比他大的，有则有，无，则为k*/ 89 //cout<<HT[j].weight<<HT[min1].weight<<" "; 90 min1=j; 91 //cout<<min1<<endl; 92 } 93 } 94 } 95 /**此时min1有两种情况：为k、不为k*/ 96 for(j=k;j<=i;j++){/**min2:也先定最前无双亲为最小，在定为最小的值即其后找除去min1小于等于最小的；此时包括min1不为k的情况和min1为k且min2在后面找到相应值的情况*/ 97 if(j==min1){ 98 continue; 99 } 100 if(HT[j].parent==0){ 101 if(HT[j].weight<=HT[min2].weight){ 102 min2=j; 103 } 104 } 105 } 106 if(min2==k&&min1==k){/**此时为min1为k且min2在后面找不到k的情况*/ 107 for(k=1;k<=i;k++){ 108 if(HT[k].parent==0&&k!=min1){/**重新找初态，及最前除去min1=k和有双亲的结点*/ 109 j=k; 110 min2=k; 111 break; 112 } 113 } 114 for(j=k+1;j<=i;j++){/**同于min1的找法*/ 115 if(HT[j].parent==0){ 116 if(HT[j].weight<HT[min2].weight){ 117 min2=j; 118 } 119 } 120 } 121 } 122 s1=min1; 123 s2=min2; 124 //cout<<s1<<" "<<s2<<endl; 125 return; 126 } 127 128 void BuildHuffmanTree(HuffmanTree &HT,int *w,int n){/**建立Huffman树*/ 129 if(n<=1){ 130 cout<<"字符个数不大于1，无法构成Huffman树及相应的Huffman编码！！"<<endl; 131 return; 132 } 133 //cout<<w[0]<<w[1]<<w[2]<<w[3]<<endl; 134 int m=2*n-1; 135 int i; 136 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/**0号未用,便于直接理解之后的select的位置范围，外层的text[],w[]运用0号位，对应关系注意**/ 137 for(i=1;i<=n;i++){ /**1...n的权即是叶子结点输入Huffman树**/ 138 HT[i].weight=w[i-1];/**w[0]已用，HT[0]未用*/ 139 HT[i].lchild=HT[i].rchild=HT[i].parent=0; 140 } 141 for(;i<=m;i++){/**其他结点初赋值为0**/ 142 HT[i].weight=HT[i].lchild=HT[i].rchild=HT[i].parent=0; 143 } 144 //cout<<HT[1].weight<<HT[2].weight<<HT[3].weight<<HT[4].weight<<endl; 145 int s1=0,s2=0; 146 for(i=n+1;i<=m;i++){ 147 Select(HT,i-1,s1,s2);/**实现挑选，找到最小的两个值，且s1<=s2，注意事项详见Select()**/ 148 HT[s1].parent=i; 149 HT[s2].parent=i; 150 HT[i].lchild=s1; 151 HT[i].rchild=s2; 152 HT[i].weight=HT[s1].weight+HT[s2].weight; 153 //cout<<HT[s1].weight<<"+"<<HT[s2].weight<<"="<<HT[i].weight<<endl; 154 } 155 return; 156 } 157 158 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n){/**Huffman编码，生成HC，编码存储于HC*/ 159 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));/**HC[0]不用，与Huffman树相对应*/ 160 char *cd=(char *)malloc(n*sizeof(char));/**开n个，即叶子结点数*/ 161 cd[n-1]=' ';/**从后向前添加01编码，start记录01编码字符数组的有效首地址，注意个数、长度关系*/ 162 int start; 163 int i,c,f; 164 for(i=1;i<=n;i++){ 165 start=n-1; 166 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){ 167 if(HT[f].lchild==c){ 168 cd[--start]='0';/**先自减，在存入10编码*/ 169 } 170 else{ 171 cd[--start]='1'; 172 } 173 } 174 HC[i]=(char *)malloc((n-start)*sizeof(char)); 175 strcpy(HC[i],&cd[start]); 176 } 177 free(cd); 178 return; 179 } 180 181 void BuildCodeFiles(HuffmanCode HC,char text[],int n){/**建立正文的编码文件的函数*/ 182 FILE *fp1,*fp2; 183 char filename1[20]; 184 char filename2[20]; 185 char ch; 186 int find; 187 cout<<"输入正文文件名："<<endl; 188 cin>>filename1; 189 getchar(); 190 while((fp1=fopen(filename1,"r"))==NULL){ 191 cout<<"正文文件无法打开，重新输入："<<endl; 192 cin>>filename1; 193 getchar(); 194 } 195 cout<<"输入正文编码存储的文件名："<<endl; 196 cin>>filename2; 197 getchar(); 198 while((fp2=fopen(filename2,"w"))==NULL){ 199 cout<<"文件打开失败，重新输入文件名："<<endl; 200 cin>>filename2; 201 getchar(); 202 } 203 ch=getc(fp1); 204 while(feof(fp1)==0){ 205 for(find=0;find<n;find++){ 206 if(ch==text[find]){ 207 //cout<<text[find]<<HC[find+1]; 208 int i=0; 209 while(HC[find+1][i]!=' '){ 210 putc(HC[find+1][i],fp2); 211 i++; 212 } 213 break; 214 } 215 } 216 ch=getc(fp1); 217 } 218 fclose(fp1); 219 fclose(fp2); 220 return; 221 } 222 223 void TranlateCode(HuffmanTree HT,char text[],int n){/**代码文件的译码函数,直接输入？存入译文文件？。根据Huffman树遍历思想找。根据HC找？*/ 224 FILE *fp; 225 char filename[20]; 226 char ch; 227 int find=2*n-1; 228 229 cout<<"输入待破译代码文件名："<<endl; 230 cin>>filename; 231 getchar(); 232 233 while((fp=fopen(filename,"r"))==NULL){ 234 cout<<"代码文件读取失败，重新输入文件名："<<endl; 235 cin>>filename; 236 getchar(); 237 } 238 239 cout<<"译文内容:"<<endl; 240 ch=getc(fp); 241 while(feof(fp)==0){ 242 if(HT[find].lchild==0&&HT[find].rchild==0){ 243 cout<<text[find-1];/**生成译文文件操作：FILE fp2;putc(text[find-1],fp2);*/ 244 ch=getc(fp); 245 find=2*n-1;/**重新赋值，从Huffman树的最高点遍历*/ 246 continue; 247 } 248 if(ch=='0'){ 249 find=HT[find].lchild; 250 } 251 else if(ch=='1'){ 252 find=HT[find].rchild; 253 } 254 else{ 255 cout<<"代码文件内容有误，无法破译。"<<endl; 256 exit(0); 257 } 258 259 if(HT[find].lchild==0&&HT[find].rchild==0){/**这段不能少！若少，上部分代码find下指，若这里不判断，直接读取ch，循环继续，再判断，若恰为叶子结点，再读取ch，数据替代*/ 260 cout<<text[find-1]; 261 ch=getc(fp); 262 find=2*n-1; 263 continue; 264 } 265 ch=getc(fp); 266 } 267 cout<<endl; 268 fclose(fp); 269 return; 270 } 271 272 int main() 273 { 274 int i=0,n; 275 char text[100]={0}; 276 int w[100]={0}; 277 char goal; 278 HuffmanTree HT; 279 HuffmanCode HC; 280 menu(); 281 cin>>goal; 282 getchar(); 283 while(goal!='0'){ 284 switch(goal){ 285 case '1': for(i=0;i<100;i++){ 286 text[i]=0; 287 w[i]=0; 288 } 289 n=Count(text,w); 290 cout<<"该电文有"<<n<<"种字符，字符和对应的权值如下："<<endl; 291 cout<<"字符"<<" "<<"权值"<<endl; 292 for(i=0;i<n;i++){ 293 cout<<" "<<text[i]<<" "<<" "<<w[i]<<endl; 294 } 295 cout<<"回车继续..."<<endl; 296 getchar(); 297 menu(); 298 cin>>goal; 299 getchar(); 300 break; 301 case '2': free(HT); 302 cout<<"建立Huffman树："<<endl; 303 BuildHuffmanTree(HT,w,n); 304 cout<<"Huffman编码树："<<endl; 305 for(i=1;i<=2*n-1;i++){ 306 cout<<HT[i].weight<<" "; 307 } 308 cout<<endl; 309 cout<<"回车继续..."<<endl; 310 getchar(); 311 menu(); 312 cin>>goal; 313 getchar(); 314 break; 315 case '3': cout<<"实现Huffmancode编码函数"<<endl; 316 free(HC); 317 HuffmanCoding(HT,HC,n); 318 cout<<"字符与对应的Huffman编码如下："<<endl; 319 for(i=1;i<=n;i++){ 320 cout<<text[i-1]<<":"<<HC[i]<<endl; 321 } 322 cout<<"回车继续..."<<endl; 323 getchar(); 324 menu(); 325 cin>>goal; 326 getchar(); 327 break; 328 case '4': BuildCodeFiles(HC,text,n); 329 cout<<"回车继续..."<<endl; 330 getchar(); 331 menu(); 332 cin>>goal; 333 getchar(); 334 break; 335 case '5': cout<<"实现TranlateCode函数"<<endl; 336 TranlateCode(HT,text,n); 337 cout<<"回车继续..."<<endl; 338 getchar(); 339 menu(); 340 cin>>goal; 341 getchar(); 342 break; 343 case '0': break; 344 default:cout<<"不合法输入，没有该操作！请重新输入："<<endl; 345 cin>>goal; 346 getchar(); 347 break; 348 } 349 } 350 return 0; 351 }
同样也有顺序和链式的分类，区别在于父子关系的传递：顺序结构是利用静态数组本身的线性关系，用数组下标表示双亲和左右孩子的关系；链式结构是利用结构体中定义出特定的指针域来指向双亲或是左右孩子。一般没有什么特殊要求和目的，顺序结构常用一些。