树结构及其应用

《树结构及其应用》由会员分享，可在线阅读，更多相关《树结构及其应用（12页珍藏版）》请在装配图网上搜索。

1、中南大学数据结构实验报告题目：树结构及其应用学生姓名：张雨欣学 号：0902150323指导老师：余腊生学 院：信息科学与工程学院专业班级：计科工试1501班完成时间：2016年12月27日指导老师评定：签名：需求分析二叉树的建立与遍历（验证性实验）11.问题描述：建立一棵二叉树，并对其进行遍历（先序，中序和后序），打印输出遍历结果基本要求：从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以 先序来建立），并采用递归算法对其进行遍历（先序，中序和后序）， 将遍历结果扣印输出。测试数据：AB. CE. . G. D. F. H.则输出结果为：先序为ABCEGDFH,中序为BECGAD

2、FH, 后序为EGCBHFDA源程序#include#include #include typedef int DataType;typedef stnict NodeDataType data;stnict Node *LChild;stnict Node *RChild; BitNode, * BitTiee;void CreatBiTiee（BitTiee *bt）用扩展先序遍历序列创建二义树，如果是#当前树 根置为空，否则申请一个新节点char ch;ch=getchar();if(ch=,.,)*bt=NULL;else*bt=(BitTree)malloc(sizeof(BitNo

3、de);(*bt)-data=ch;CreatBiTree(&(*bt)-LChild);CreatBiTree(&(*bt)-RChild);)void Visit(char ch)/访问根节点printf(,r%c ”,ch);)void PieOrdei(BitTiee root) /*先序遍历二又树,root为指向二义树(或某一子树) 根结点的指针*/if(root!=NULL)Visit(root -data); /*访问根结点 */PreOrder(ioot -LChild); /*先序遍历左子树*/PreOider(ioot -RCluld); /* 先序遍历右子树 */)voi

4、d LiOider(BitTiee root)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)niOider(ioot -LCluld); /*中序遍历左子树*/Visit(root -data);/* 访问根结点 */IiiOider(root -RChild); /* 中序遍历右子树*/)void PostOrdei(BitTiee root)/*后序遍历二又树，root为指向二义树(或某一子树)根结点的指针*/if(root!=NULL)PostOrder(root -LChild); /* 后序遍历左子树*/PostOidei(root

5、 -RChild); /*后序遍历右子树*/Visit(root -data);/* 访问根结点 */mt PostTieeDepth(BitTiee bt) 后序遍历求二又树的高度递归算法mt lil.lujnax;if(bt!=NULL)(hl=PostTreeDepth(bt-LChiId); 求左子树的深度ln-PostTieeDepth(bt-RCluld); 求右子树的深度max=hllii?hl:lii-; 得到左、右子树深度较大者ietuin(max+l); 返回树的深度else lennn(O);如果是空树，则返回0 void PiintTiee(BitTiee Boot.i

6、iit iiLayer) 按燧向树状打印的二义树int i;if(Boot=NULL) return;PimtTree(Boot-RChild4iLayef+l);fbi(i=O;idata);PimtTree(Boot-LChild .nLayei+1);)void mam()BitTree T;mt h;mt layer;mt treeleaf;layei-0;pnntf(”清输入二又树中的元素(以扩展先序遍历序列输入，其中.代表空子树) CieatBiTiee(&T);pnntf(”先序遍历序列为:”)；PieOrder(T);prmtf(uii中序遍历序列为:，InOider(T);后

7、序遍历序列为:”)；PostOidei(T);h=PostTieeDepth(T);pnntf(HiiTlie depth of this tree is:%diin,h);PriiitTree(T4ayeij;赫夫曼编码(综合性实验)问题描述：设某编码系统共有n个字符，使用频率分别为wl,w2，,wn,设计一 个不等长的编码方案，使得该编码系统的空间效率最好。基本要求：I：初始化(Initialization)o从终端读入字符集大小n,以及n个 字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码(Encoding)。利用以建好的哈夫曼树(如不在内存，则从文 件hfmTre

8、e中读入)，对文件To Be Tran中的正文进行编码，然后将 结果存入文件CodeFile中。D：译码(Decoding)o利用已建好的哈夫曼树将文件Code File中的 代码进行译码，结果存入文件Text File中。P：印代码文件(Print)o将文件Code File以紧凑格式显示在终端 上，每行50个代码。同时将此字符形式的编码文件写入文件Code Print 中。T：印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观 的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫 曼树写入文件Tree Print中。测试数据：由读者依据软件工程的测试技术自己确定

9、，注意测试边界数据。实现提示：利用赫夫曼编码树求得最佳的编码方案（1）文件CodeFile的基类可以设为字节型（2）用户界面可以设计为菜单形式，除显示上述功能符号外，还应 显示Q,表示退出，请用户键入一个选择功能符，此功能执行 完毕后再显示此菜单，直至某次用户选择了E为止（3）在程序的一次执行过程中，第一次执行I,D或C命令之后，赫 夫曼树已经在内存了，不必再读入，每次执行时不一定执行I 命令，因为hrmTree可能早以建好。源代码#include #include #include #define MAXLEN 100typedef structint weight;int Ichild;i

10、nt rchild;int parent;char key;Jhtnode;typedef htnode hfmtMAXLEN;int n;void inithfmt（hfmt t）乂寸结构体进行初始化int i;print);printf(Hprintf(N*printf(Hn 请输入 n=H)； scanf(,%d,/&n);getchar();for(i=0;i2*n-l;i+)/对结构体进行初始化ti.weight=O;ti.lchild=-l;ti.rchild=-l;ti.parent=-l;)printf(n“);)void inputweight(hfmt t)输入函数int

11、w;/w表示权值int i;char k;/k表示获取的字符for(i=0;in;i+)printf(“请输入第d个字符:嘴+1);scanf(c“,&k);getchar();ti.key=k;printf(“请输入第d个字符的权值:”,i+1);scanf(%d,&w);getchar();ti.weight=w;printfCAn-);)void selectmin(hfmt t,int ijnt *pl,int *p2)选中两个权值最小的函数long minl=999999;long min2=999999;int j；for(j=0;jtj.weight)minl=tj.weight

12、;*pl=j;)for(j=0;jtj.weight & j!=(*pl)注意 j!=(*pl) (min2=tj.weight;*p2=j；)void creathfmt(hfmt t)/创建哈夫曼树的函数int i,pl,p2;inithfmt(t);inputweight(t);for(i=n;i2*n-l;i+)selectmin(t,i-l,&pl,&p2);tpl.parent=i;tp2.parent=i;ti.lchild=pl;ti.rchild=p2;ti.weight=tpl.weight+tp2.weight;void printhfmt(hfmt t)打印哈夫曼树in

13、t i;printf(MnM);pri ntf (11 *哈 夫 曼 编构* * *、n”).printf(tt权重t父母t左孩子t右孩子t字符t);for(i=0;i2*n-l;i+)printf(”n)；printf(tt%dt%dt%dt%dt%c,ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key);printf(nnu);printf(nn);void hfmtpath(hfmt t,int ijnt j)编码的重要哈夫曼树路径递归算法int a,b;a=i；b=j=ti.parent;if(tj.parent!=-l)i=j；hfmtpat

14、h(tJJ);if(tb.lchild=a)printf(O);elseprintf(T)；)void phfmnode(hfmtt)/对字符进行初始编码int i,j,a;n”）；夫 曼 编 码printf(npri ntf(11 *”).for(i=0;in;i+)j=0;printf(n);printf(tt%ct,ti.keyzti.weight);hfmtpath(tJJ);printf(nn);void encoding(hfmt t)对用户输入的电文进行编码char r1000;/ffl来存储输入的字符串int i,j；printf(nn请输入需要编码的字符:)；gets(r);

15、printf(“编码结果为:”);for(j=0;rj!=0;j+)for(i=0;in;i+)if(rj=ti.key)hfmtpath(t,ij);printfCXn);void decoding(hfmt t)对用户输入的密文进行译码 char r100;int ijjen;j=2*n-2;/j初始从树的根节点开始 printf(nn请输入需要译码的字符串：“); gets(r);len=strlen(r);printf(译码的结果是:);for(i=0;ilen;i+)if(ri=。)(j=tj.lchild;if(tj.lchild=-l)(printf(%c,tj.key); j=

16、2*n-2;else if(ri=,l,)(j=tj.rchild;if(tj.rchild=-l)(printf(%c,tj.key); j=2*n-2;printf(nn);int main()int i,j;hfmt ht;char flag;printf(|I * |n”)I哈夫曼编码课程设计|n)；* n”)IlnM)；printf(Mprintf(Hprintf(Nprintf(Ncreathfmt(ht);printhfmt(ht);phfmnode(ht);printf(nn);printf(M* 编 码 & 译 码 & 退 *”).printf(n 1编码t 2 t 译码t

17、0退出);printf(n 您的选择：)；flag=getchar();getchar();while(flag!=O)if(flag=T)encoding(ht);else if(flag=,2,)decoding(ht);elseprintf(“您的输入有误，请重新输入o nH)； printf(”n* 编码 & 译码 & 退 *”).printf(n 1编码t 2 t 译码t 0退出”)；printf(nn 您的选择：);flag=getchar();getchar();printf(nnn);printf(”*欢迎使用林左权的哈夫曼编码系 * *n”).-An11)；printf(sy

18、stem(,pause,1);功能演示C:User5AirDocumentsC-FreeTemp未命S10.exe”!哈夫曼编码课程设计：请输入n =5蒂默黯尊费权佳，莆歉囊牛辜彝备权值 牌蕾爆梅篇权值：3 31酸黝暮费权值：5 瞧燧洱骚又佳3权重17353471219Q - 2345王牌拼音输入法至心得体会通过这次实验使我发现我是编程能力较差，而且对于二义树的知 识学的也不是很好。使得在编程时，发现有很多地方不是很懂，经常要参考课本、 源代码和上网查资料，才勉强吧这个程序编下来。所以在以后的学习中要多看书, 多练习一些编程题，提高自己的编程能力，争取做到能够单独编程。这样才能真 正学到的有用的知识。1、实验中经常会出现前后字符不一致的情况，主要原因是自己比较马虎，平时 编程比较少，遇到比较长的程序，就容易出错。解决方法：应多加练习编程，要仔细认真。2、用给的参考方法建立二义树时；总是在编译和链接时无错，但无法运行。解决方法：参照课本，改用递归建立，程序就可正常运行。3、输入时出错，不会输入。解决办法：当结点左右孩子不全时，缺儿个就要打儿个空格。4、在计算结点数时，由于递归的知识学的不是很好，不会计算。解决方法：改为先计算每层结点数，然会再相加即可。