验证性实验7：二叉树子系统

《验证性实验7：二叉树子系统》由会员分享，可在线阅读，更多相关《验证性实验7：二叉树子系统（11页珍藏版）》请在装配图网上搜索。

1、验证性实验7:二叉树子系统1. 班级学号BX100420姓名施程程成绩实验目的(1) 掌握二叉树的特点及其存储的方式。(2) 掌握二叉树的创建和显示方法。(3) 复习二叉树遍历的概念，掌握二叉树遍历的基本方法(4) 掌握求二叉树的叶结点数、总结点数和深度等基本算法。2. 实验内容(1) 按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。(2) 编写前序遍历、中序遍历、后序遍历、层次遍历程序。(3) 编写求二叉树的叶结点数、总结点数和深度的程序。(4) 设计一个选择式菜单，以菜单方式选择下列操作。二叉树子系统*1建二叉树2凹入显示历历遍遍序序先中5 后序遍历层次遍历求叶子数.7*8

2、-求结点数*9-求树深度*请选择菜单号(0-9):3. 实验步骤：(1) 输入并调试程序；(2) 按下图建立二叉树；二叉树子系统*1-建二叉树*2-凹入显示*3-先序遍历*4-中序遍历*5-后序遍历*6-层次遍历*7-求叶子数*8-求结点数*9-求树深度*0-返回*请选择菜单号：1请输入按先序建立二叉树的结点序列：说明：0代表后继结点为空，请逐个输入，按回车键输入下一结点。请输入根结点：a请输入a结点的左子结点：b请输入b结点的左子结点：d请输入d结点的左子结点：0请输入d结点的右子结点：0请输入b结点的右子结点：0请输入a结点的右子结点：c请输入c结点的左子结点：e请输入e结点的左子结点：0

3、请输入e结点的右子结点：0请输入c结点的右子结点：f请输入f结点的左子结点：0请输入f结点的右子结点：0检查凹入法显示的二叉树是否正确；二叉树子系统*1-建二叉树*2-凹入显示*3-先序遍历*4-中序遍历*5-后序遍历*6-层次遍历*7-求叶子数*8-求结点数*9-求树深度*0-返回*请选择菜单号：2凹入表示法：(3) abdcef按回车键返回主菜单！检查其他算法的正确性举例：二叉树子系统*1-建二叉树*2-凹入显示*3-先序遍历*4-中序遍历*5-后序遍历*6-层次遍历*7-求叶子数*8-求结点数*9-求树深度*0-返回*请选择菜单号：3该二叉树的先序遍历序列为：abdcef实验程序#inc

4、lude#defineTREEMAX100typedefstructBTchardata;BT*lchild;BT*rchild;BT;BT*CreateTree();voidShowTree(BT*T);voidPreorder(BT*T);voidPostorder(BT*T);voidLevelorder(BT*T);voidInorder(BT*T);voidLeafnum(BT*T);voidNodenum(BT*T);intTreeDepth(BT*T);intcount=0;voidmain()(BT*T=NULL;charch1,ch2,a;ch1=y;while(ch1=y|

5、ch1=y)(printf(n);printf(ntt二叉树子系统);printf(ntt*);printf(ntt*1-建二叉树printf(ntt*2-凹入显示printf(ntt*3-先序遍历历历历数数度回遍遍遍子点深序序次叶结树中后层求求求返A)A)A)A7printf(ntt*printf(ntt*printf(ntt*printf(ntt*printf(ntt*printf(ntt*printf(ntt*printf(ntt*);printf(ntt请选择菜单号(0-9):);scanf(%c”,&ch2);getchar();printf(n);switch(ch2)(case1

6、:printf(ntt请按先序序列输入二叉树的结点：n);printf(-ntt说明：输入结点(0代表后继结点为空)后按回车.n);printf(ntt请输入根结点：);T=CreateTree();printf(ntt二叉树成功建立!n);break;case2:ShowTree(T);break;case3:printf(ntt该二叉树的先序遍历序列为：);Preorder(T);break;case4:printf(ntt该二叉树的中序遍历序列为：);Inorder(T);break;case5:printf(ntt该二叉树的后序遍历序列为：);Postorder(T);break;ca

7、se6:printf(ntt该二叉树的层次遍历序列为：);Levelorder(T);break;case7:count=0;Leafnum(T);printf(ntt该二叉树有%d个叶子。n”,count);break;case8:count=0;Nodenum(T);printf(ntt该二叉树总共有%d个结点。n”,count);break;case9:printf(ntt该树的深度是：d”,TreeDepth(T);break;case0:ch1=n;break;default:printf(ntt*请注意：输入有误！*);if(ch2!=0)printf(nntt按【Enter】键继

8、续，按任意键返回主菜单！n);a=getchar();if(a!=xA)getchar();ch1=n;BT*CreateTree()BT*t;charx;scanf(%c”,&x);getchar();if(x=0)t=NULL;elset=newBT;t-data=x;printf(ntt请输入c结点的左子结点：,t-data);t-lchild=CreateTree();printf(ntt请输入c结点的右子结点：,t-data);t-rchild=CreateTree();returnt;voidPreorder(BT*T)(if(T)(printf(%3c”,T-data);Preo

9、rder(T-lchild);Preorder(T-rchild);voidInorder(BT*T)(if(T)(Inorder(T-lchild);printf(%3c,T-data);Inorder(T-rchild);voidPostorder(BT*T)(if(T)(Postorder(T-lchild);Postorder(T-rchild);printf(%3c,T-data);voidLevelorder(BT*T)(inti,j;BT*q100,*p;p=T;if(p!=NULL)i=1;qi=p;j=2;while(i!=j)p=qi;printf(%3c,p-data);

10、if(p-lchild!=NULL)qj=p-lchild;j+;if(p-rchild!=NULL)qj=p-rchild;j+;i+；voidLeafnum(BT*T)(if(T)(if(T-lchild=NULL&T-rchild=NULL)count+;Leafnum(T-lchild);Leafnum(T-rchild);voidNodenum(BT*T)(if(T)(count+;Nodenum(T-lchild);Nodenum(T-rchild);intTreeDepth(BT*T)(intldep,rdep;if(T=NULL)return0;else(ldep=TreeDe

11、pth(T-lchild);rdep=TreeDepth(T-rchild);if(ldeprdep)returnldep+1;elsereturnrdep+1;voidShowTree(BT*T)(BT*stackTREEMAX,*p;intlevelTREEMAX2,top,n,i,width=4;if(T!=NULL)(printf(ntt凹入表示法:ntt);top=1;stacktop=T;leveltop0=width;while(top0)(p=stacktop;n=leveltop0;for(i=1;idata);for(i=n+1;irchild!=NULL)(top+;st

12、acktop=p-rchild;leveltop0=n+width;leveltop1=2;if(p-lchild!=NULL)(top+;stacktop=p-lchild;leveltop0=n+width;leveltop1=1;-!乂*E:如数据卷构VDaBugk1ST-。言牲二叉制子不统网示用AA*教度回叉显遍舌深建凹先HW层扳Z-IZ-I加21请送择粟鱼号39),1请按先序序列输入二黑树拘结点，说明；输入结点侦代表后兰蝶点为空后按回车.请输入根结点:*请输&结点的左子结点;b云.黔气粼据登祠顼eibyk宝警T.5。请瑜入株结就的左子结点I请输入b结点的左子结点:请输如结点的左子结点

13、,请输入次吉点的右孑结点:请输入L结点的右子结总请输入q吉点的右子结点:请输入。结点的左子结点:请输入巳结点的左子结点:请输入e结点的右子结点:请输入。结点的右子结点,请输入结点的左子结点|.请输A?姑点的右子结点;凹入表示法;技UntCr键继缕，投意键返回主菜单I*E:气敏据纸柄5好11右I蜜碧7-exeMI-MIM*M野*#*liMMM-二旦*E:匕数据卷桐5皇111宫1实碧T一fixe技Unter携继续，投仁色键返回主菜单|-AW子美缆-囱下万历历历教数在K回-叉显着遍遍言注三入岸序次霉树-建凹先中后层-请选择菜单号（0-9）=3该二叉树的先序遍历序列为；abdqgr技Enter键继绣，

14、投任意键返回主菜单IHi-Ini2d技Enter键继停，长仁吏键逐回王菜单I二曳例子套茨:T示历历历历数数百甘曳显遍遍遍遍否深二入序JT序次髯树建凹先中后层-请选择某首号09）=4该二叉树的中序遍历序?U为IdbaBcF技EHk】键继缕，投住意键返回主菜单I*E:如数据卷构VDa1ST-cxc技Enter携继续，投任色键返回主菜单i-AW子系统*密不万而历历教数度回叉显着遍遍言注二入序序序次霉树建凹先中后层请选择菜单号（0-9）=g该二实御的后序遍历序列为：dbeFca技E5键继绣，投任意键盘回主菜单|Hi-In2d幻任：、数髭结物LDolm.l早:玲T.ec：技Enter键继停，长仁吏键逐回

15、王菜单I二曳例子套茨:T示历历历历数数百甘曳显遍遍遍遍否深二入序JT序次髯树建凹先中后层-请选择菜单号（6-9）.6该二叉树的层次遍历序列为】bcdbf技lEnl键继缕，投住意键返回主菜单I-Ini2d球.土I数据结袖LlUlmgl敏娶T-g。-技【EnUiJ键纸疫版任意鹿回主菜单I-XW子系统珂下万历历历教教#K回叉遍碧淬二入序序序长霉树建凹先中后层wig-树示历历历历数数商V显遍遍遍遍否深二入序序JT次雾树建凹先中后层返-请迭择菜单号（0-9）=P该二曳树初个叶丑技E5键继绣，投任意键盘回主菜单|:数据姑物LDKh诳织芸T.exe*覆【&包3禅4,1亲意健魔回主菜单I诸选择菜自号（6-?）

16、:e该二灵树总共郁个结点.技花此“】键继缕，投住意键返回主菜单I*E:如数据卷构VDaBugk1ST-cxc|n|m技Enter携继续，投任色键返回主菜单|密不万而历历教数度回叉显着遍遍言注二入序序序次霉树建凹先中后层-AW子系统请选择菜单号（0-9）=9该树的深度是；3|口1乂技ERCet-键继绣，按任意键盘回主菜单I技*E:，敏据登fyDKii右k蜜碧7-exe请选括荣苴号（*T）9该树的深度是：3按槌继续，按任蕙键返回全菜单|5洞示历可为*数春同-叉显遍遍遍浑*建凹先中后层1043Z-I*MV-HXXSEpssaovkeytocontinue6.实验小结本章要求我们掌握的是二叉树的特点、存储方式、创建、显示、遍历以及节点数等计算方法。这个实验要求设计的是一颗二叉树，要求能用凹入法显示二叉树的结构，能读出前序遍历、中序遍历、后序遍历和层次遍历，以及会求解叶节点数、总节点数和树的深度。在输入程序的时候有些错误，但在编译和构建的时候都改正了，执行起来很方便。程序中在后面注释的帮助下也能知道相应程序的作用，结合上课听到的知识更容易理解了，这对我是一个不小的帮助。当然，在编译时发现错误的时候，改正也能帮我巩固记忆，让我知道什么地方错了，也能更好的学习并记住，争取以后不会再犯同样的错误。总的来说，本次实验还是成功的。