树和二叉树的实现.doc

《树和二叉树的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、广州大学学生实验报告开课学院及实验室：实验楼室2011年月日学院计算机科学与教育软件学院年级、专业、班计算机大类094班姓名潘永航学号实验课程名称数据结构实验成绩实验项目名称实验二树和二叉树的实现指导老师一、实验目的树和二叉树的实现二、实验设备1．计算机2．windows操作系统，vc6.0三、实验要求1、设计一个程序，根据二叉树的先根序列和中根序列创建一棵用左右指针表示的二叉树2.根据哈夫曼算法创建哈夫曼树，并求树中每个外部结点的编码3.设计一个程序，把中缀表达式转换成一棵二叉树，然后通过后序遍历计算表达式的值//shiyan1#include

2、o.h>#include#includestructbitree{chardata;structbitree*lchild,*rchild;};structbitree*createbitree(char*xian,int*i,char*zhong,intm,intn);voidoreordertraverse(structbitree*t);main(){charxian[50],zhong[50];structbitree*t;inti=0;printf("按照先序输入");gets(xian);printf

3、("按照中序输入");gets(zhong);t=createbitree(xian,&i,zhong,0,strlen(zhong)-1);oreordertraverse(t);}voidoreordertraverse(structbitree*t){if(t){printf("%c",t->data);oreordertraverse(t->lchild);oreordertraverse(t->rchild);}elseprintf("0");}structbitree*createbitree(char*xian,int*i,char*zh

4、ong,intm,intn){intj;for(j=m;j<=n;j++)if(zhong[j]==xian[*i]){structbitree*t;if(!(t=(structbitree*)malloc(sizeof(structbitree))))exit(1);t->data=xian[*i];++*i;t->lchild=createbitree(xian,i,zhong,m,j-1);t->rchild=createbitree(xian,i,zhong,j+1,n);return(t);}return(NULL);}#include

5、o.h>#defineMAXBIT10#defineMAXVALUE10000#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1typedefstruct{intbit[MAXBIT];intstart;}Hcodetype;typedefstruct{intweight;intparent;intlchild;intrchild;}Hnodetype;voidhuffmantree(Hnodetypehuffnode[MAXNODE],intn){inti,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i++

6、){huffnode[i].weight=0;huffnode[i].parent=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}for(i=0;i

7、j].parent==-1){m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;}elseif(huffnode[j].weight

8、+i].rchild=x2;}}voidmain(){Hnodet