树结构及其应用

中南大学数据结构实验报告题目：树结构及其应用学生姓名：张雨欣学号：0902150323指导老师：余腊生学院：信息科学与工程学院专业班级：计科工试1501班完成时间：2016年12月27日指导老师评定：签名：需求分析二叉树的建立与遍历（验证性实验）11'.二叉树的建立与遍历（验证性实验）11'.问题描述：建立一棵二叉树，并对其进行遍历（先序，中序和后序），打印输出遍历结果基本要求：从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序，中序和后序），将遍历结果扣印输出。测试数据：AB.CE..G.D.F.H..则输出结果为：先序为ABCEGDFH,中序为BECGADFH,后序为EGCBHFDA源程序#include<stdio.11>#include<malloc.h>#include<como.h>typedefintDataType;typedefstnictNode{DataTypedata;stnictNode*LChild;stnictNode*RChild;}BitNode,*BitTiee;voidCreatBiTiee（BitTiee*bt）〃用扩展先序遍历序列创建二义树，如果是#当前树根置为空，否则申请一个新节点〃charch;ch=getchar();if(ch=,.,)*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));})voidVisit(charch)//访问根节点{printf(,r%c”,ch);)voidPieOrdei(BitTieeroot)/*先序遍历二又树,root为指向二义树(或某一子树)根结点的指针*/{if(root!=NULL){Visit(root->data);/*访问根结点*/PreOrder(ioot->LChild);/*先序遍历左子树*/PreOider(ioot->RCluld);/*先序遍历右子树*/})voidLiOider(BitTieeroot)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/{if(root!=NULL){niOider(ioot->LCluld);/*中序遍历左子树*/Visit(root->data);/*访问根结点*/IiiOider(root->RChild);/*中序遍历右子树*/})voidPostOrdei(BitTieeroot)/*后序遍历二又树，root为指向二义树(或某一子树)根结点的指针*/{if(root!=NULL){PostOrder(root->LChild);/*后序遍历左子树*/PostOidei(root->RChild);/*后序遍历右子树*/Visit(root->data);/*访问根结点*/}}mtPostTieeDepth(BitTieebt)〃后序遍历求二又树的高度递归算法〃{mtlil.lujnax;if(bt!=NULL)(hl=PostTreeDepth(bt->LChiId);〃求左子树的深度ln-PostTieeDepth(bt->RCluld);〃求右子树的深度max=hl>lii?hl:lii-;〃得到左、右子树深度较大者ietuin(max+l);〃返回树的深度}elselennn(O);〃如果是空树，则返回0}voidPiintTiee(BitTieeBoot.iiitiiLayer)〃按燧向树状打印的二义树〃{inti;if(Boot==NULL)return;PimtTree(Boot->RChild4iLayef+l);fbi(i=O;i<nLayer;i++)pi-mtf(u”)；pmitf(u%c\n,\Boot->data);PimtTree(Boot->LChild.nLayei+1);)voidmam(){BitTreeT;mth;mtlayer;mttreeleaf;layei-0;pnntf(”清输入二又树中的元素(以扩展先序遍历序列输入，其中.代表空子树)CieatBiTiee(&T);pnntf(”先序遍历序列为:”)；PieOrder(T);prmtf(u\ii中序遍历序列为:，InOider(T);后序遍历序列为:”)；PostOidei(T);h=PostTieeDepth(T);pnntf(H\iiTliedepthofthistreeis:%d\iin,h);PriiitTree(T4ayeij;}赫夫曼编码(综合性实验)问题描述：设某编码系统共有n个字符，使用频率分别为wl,w2，…,wn,设计一个不等长的编码方案，使得该编码系统的空间效率最好。基本要求：I：初始化(Initialization)o从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码(Encoding)。利用以建好的哈夫曼树(如不在内存，则从文件hfmTree中读入)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。D：译码(Decoding)o利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。P：印代码文件(Print)o将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。T：印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：由读者依据软件工程的测试技术自己确定，注意测试边界数据。实现提示：利用赫夫曼编码树求得最佳的编码方案

（1）文件CodeFile的基类可以设为字节型（2）用户界面可以设计为菜单形式，除显示上述功能符号外，还应显示Q,表示退出，请用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了E为止（3）在程序的一次执行过程中，第一次执行I,D或C命令之后，赫夫曼树已经在内存了，不必再读入，每次执行时不一定执行I命令，因为hrmTree可能早以建好。源代码#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXLEN100typedefstruct{intweight;intIchild;intrchild;intparent;charkey;Jhtnode;typedefhtnodehfmt[MAXLEN];intn;voidinithfmt（hfmtt）〃乂寸结构体进行初始化inti;print");printf(H——printf(N******************************printf(Nprintf(H\n请输入n=H)；scanf(,,%d,,/&n);getchar();for(i=0;i<2*n-l;i++)//对结构体进行初始化{t[i].weight=O;t[i].lchild=-l;t[i].rchild=-l;t[i].parent=-l;)printf("\n“);)voidinputweight(hfmtt)〃输入函数{intw;//w表示权值inti;chark;//k表示获取的字符for(i=0;i<n;i++){printf(“请输入第％d个字符:嘴+1);scanf("％c“,&k);getchar();t[i].key=k;printf(“请输入第％d个字符的权值:”,i+1);scanf("%d",&w);getchar();t[i].weight=w;printfCAn-);))voidselectmin(hfmtt,intijnt*pl,int*p2)〃选中两个权值最小的函数{longminl=999999;longmin2=999999;intj；for(j=0;j<=i;j++)//选择最小权值字符的下标返回if(t[j].parent==-l)if(minl>t[j].weight){minl=t[j].weight;*pl=j;)for(j=0;j<=i;j++)〃选择次小权值字符的下标还回if(t[j].parent==-l)if(min2>t[j].weight&&j!=(*pl))〃注意j!=(*pl))(min2=t[j].weight;*p2=j；})voidcreathfmt(hfmtt)//创建哈夫曼树的函数{inti,pl,p2;inithfmt(t);inputweight(t);for(i=n;i<2*n-l;i++){selectmin(t,i-l,&pl,&p2);t[pl].parent=i;t[p2].parent=i;t[i].lchild=pl;t[i].rchild=p2;t[i].weight=t[pl].weight+t[p2].weight;}}voidprinthfmt(hfmtt)〃打印哈夫曼树{inti;printf(M\nM);printf(11**********************哈夫曼编构・*****************************、n”).printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");for(i=0;i<2*n-l;i++){printf(”\n")；printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);}printf("\n\nu);printf("\n\n");}voidhfmtpath(hfmtt,intijntj)〃编码的重要哈夫曼树路径递归算法

inta,b;a=i；b=j=t[i].parent;if(t[j].parent!=-l){i=j；hfmtpath(tJJ);}if(t[b].lchild==a)printf("O");elseprintf(T)；)voidphfmnode(hfmtt)//对字符进行初始编码{inti,j,a;\n”）；夫曼编码printf("\nprintf(\n”）；夫曼编码for(i=0;i<n;i++){j=0;printf("\n");printf("\t\t%c\t,,,t[i].keyzt[i].weight);hfmtpath(tJJ);}printf("\n\n");}voidencoding(hfmtt)〃对用户输入的电文进行编码{charr[1000];//ffl来存储输入的字符串inti,j；printf("\n\n请输入需要编码的字符:")；gets(r);printf(“编码结果为:”);for(j=0;r[j]!='\0';j++)for(i=0;i<n;i++)if(r[j]==t[i].key)hfmtpath(t,ij);printfC'Xn");}voiddecoding(hfmtt)〃对用户输入的密文进行译码{charr[100];intijjen;j=2*n-2;//j初始从树的根节点开始printf("\n\n请输入需要译码的字符串：“);gets(r);len=strlen(r);printf("译码的结果是:");for(i=0;i<len;i++){if(r[i]==。)(j=t[j].lchild;if(t[j].lchild==-l)(printf("%c",t[j].key);j=2*n-2;}}elseif(r[i]==,l,)(j=t[j].rchild;if(t[j].rchild==-l)(printf("%c",t[j].key);j=2*n-2;}}}printf("\n\n");}intmain(){inti,j;hfmtht;charflag;printf("|

I**********************|\n”)・I哈夫曼编码课程设计|\n")；]**********************]\n”)・Il\nMI**********************|\n”)・I哈夫曼编码课程设计|\n")；]**********************]\n”)・Il\nM)；printf(M***************************编码&&译码&&退***********************”).printf("\n[1]编码\t[2]\t译码\t[0]退出");printf("\n您的选择：")；flag=getchar();getchar();while(flag!='O')if(flag=T)encoding(ht);elseif(flag==,2,)decoding(ht);elseprintf(“您的输入有误，请重新输入o\nH)；printf(”\n***************************编码&&译码&&退***********************”).printf("\n[1]编码\t[2]\t译码\t[0]退出”)；printf(n\n您的选择：");flag=getchar();getchar();}prin