树和二叉树的实现

广州大学学生实验报告开课学院及实验室：实验楼室2011年月日学院计算机科学与教育软件学院年级、专业、班计算机大类094班姓名潘永航学号0923010089实验课程名称数据结构实验成绩实验项目名称实验二树和二叉树的实现指导老师一、实验目的树和二叉树的实现二、实验设备1．计算机2．windows操作系统，vc6.0三、实验要求1、设计一个程序，根据二叉树的先根序列和中根序列创建一棵用左右指针表示的二叉树2.根据哈夫曼算法创建哈夫曼树，并求树中每个外部结点的编码3.设计一个程序，把中缀表达式转换成一棵二叉树，然后通过后序遍历计算表达式的值//shiyan1#includestdio.h#includestdlib.h#includestring.hstructbitree{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(按照先序输入\n);gets(xian);printf(按照中序输入\n);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*zhong,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);}#includestdio.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;i2*n-1;i++){huffnode[i].weight=0;huffnode[i].parent=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}for(i=0;in;i++){printf(pleaseinput%dcharacter'sweight\n,i);scanf(%d,&huffnode[i].weight);}for(i=0;in-1;i++){m1=m2=MAXVALUE;x1=x2=0;for(j=0;jn+i;j++){if(huffnode[j].weightm1&&huffnode[j].parent==-1){m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;}elseif(huffnode[j].weightm2&&huffnode[j].parent==-1){m2=huffnode[j].weight;x2=j;}}huffnode[x1].parent=n+i;huffnode[x2].parent=n+i;huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;huffnode[n+i].lchild=x1;huffnode[n+i].rchild=x2;}}voidmain(){Hnodetypehuffnode[MAXNODE];Hcodetypehuffcode[MAXLEAF],cd;inti,j,c,p,n;printf(pleaseinputn\n);scanf(%d,&n);huffmantree(huffnode,n);for(i=0;in;i++){cd.start=n-1;c=i;p=huffnode[c].parent;while(p!=-1){if(huffnode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=huffnode[c].parent;}for(j=cd.start+1;jn;j++)huffcode[i].bit[j]=cd.bit[j];huffcode[i].start=cd.start;}for(i=0;in;i++){printf(%dcharacteris:,i);for(j=huffcode[i].start+1;jn;j++)printf(%d,huffcode[i].bit[j]);printf(\n);}}}