数据结构实验7：二叉树子系统.doc

《数据结构实验7：二叉树子系统.doc》由会员分享，可在线阅读，更多相关《数据结构实验7：二叉树子系统.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构实验7：二叉树子系统.精品文档.验证性实验7：二叉树子系统班级学号 BX100420 姓名 施程程 成绩 1实验目的（1）掌握二叉树的特点及其存储的方式。（2）掌握二叉树的创建和显示方法。（3）复习二叉树遍历的概念，掌握二叉树遍历的基本方法（4）掌握求二叉树的叶结点数、总结点数和深度等基本算法。2实验内容（1）按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。（2）编写前序遍历、中序遍历、后序遍历、层次遍历程序。（3）编写求二叉树的叶结点数、总结点数和深度的程序。（4）设计一个选择式菜单，以菜单方式选择下列操作。 二 叉

2、 树 子 系 统* 1-建 二 叉 树 *);* 2-凹 入 显 示 *);* 3-先 序 遍 历 *);* 4-中 序 遍 历 *);* 5-后 序 遍 历 *);* 6-层 次 遍 历 *);* 7-求 叶 子 数 *);* 8-求 结 点 数 *);* 9-求 树 深 度 *);* 0-返 回 *);请选择菜单号（0-9）：3实验步骤：（1）输入并调试程序；（2）按下图建立二叉树；abcdef 二 叉 树 子 系 统 * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * *

3、7-求 叶 子 数 * * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * 请选择菜单号：1请输入按先序建立二叉树的结点序列：说明：0代表后继结点为空，请逐个输入，按回车键输入下一结点。请输入根结点：a请输入a结点的左子结点：b请输入b结点的左子结点：d请输入d结点的左子结点：0请输入d结点的右子结点：0请输入b结点的右子结点：0请输入a结点的右子结点：c请输入c结点的左子结点：e请输入e结点的左子结点：0请输入e结点的右子结点：0请输入c结点的右子结点：f请输入f结点的左子结点：0请输入f结点的右子结点：0（3）检查凹入法显示的二叉树是否正确； 二 叉 树 子 系 统

4、 * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * * 7-求 叶 子 数 * * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * 请选择菜单号：2凹入表示法： a b d c e f 按回车键返回主菜单! （4）检查其他算法的正确性举例： 二 叉 树 子 系 统 * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * * 7-求 叶 子 数

5、* * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * 请选择菜单号：3该二叉树的先序遍历序列为：a b d c e f4实验程序 #include#define TREEMAX 100typedef struct BTchar data;BT *lchild;BT *rchild;BT;BT *CreateTree();void ShowTree(BT *T);void Preorder(BT *T);void Postorder(BT *T);void Levelorder(BT *T);void Inorder(BT *T);void Leafnum(BT *T)

6、;void Nodenum(BT *T);int TreeDepth(BT *T);int count=0;void main()BT *T=NULL;char ch1,ch2,a;ch1=y;while(ch1=y|ch1=y)printf(n);printf(ntt 二叉树子系统);printf(ntt*);printf(ntt* 1-建 二 叉 树 *);printf(ntt* 2-凹 入 显 示 *);printf(ntt* 3-先 序 遍 历 *);printf(ntt* 4-中 序 遍 历 *);printf(ntt* 5-后 序 遍 历 *);printf(ntt* 6-层 次

7、遍 历 *);printf(ntt* 7-求 叶 子 数 *);printf(ntt* 8-求 结 点 数 *);printf(ntt* 9-求 树 深 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(ntt 请选择菜单号（0-9）：);scanf(%c,&ch2);getchar();printf(n);switch(ch2)case 1:printf(ntt请按先序序列输入二叉树的结点：n);printf(ntt说明：输入结点(0代表后继结点为空)后按回车.n);printf(ntt请输入根结点：);T=CreateTree();printf(n

8、tt二叉树成功建立！n);break;case 2:ShowTree(T);break;case 3:printf(ntt该二叉树的先序遍历序列为：);Preorder(T);break;case 4:printf(ntt该二叉树的中序遍历序列为：);Inorder(T);break;case 5:printf(ntt该二叉树的后序遍历序列为：);Postorder(T);break;case 6:printf(ntt该二叉树的层次遍历序列为：);Levelorder(T);break;case 7:count=0;Leafnum(T);printf(ntt该二叉树有%d个叶子。n,count

9、);break;case 8:count=0;Nodenum(T);printf(ntt该二叉树总共有%d个结点。n,count);break;case 9:printf(ntt该树的深度是：%d,TreeDepth(T);break;case 0:ch1=n;break;default:printf(ntt*请注意：输入有误！*);if(ch2!=0)printf(nntt按【Enter】键继续，按任意键返回主菜单！n);a=getchar();if(a!=xA)getchar();ch1=n;BT *CreateTree()BT *t;char x;scanf(%c,&x);getchar

10、();if(x=0)t=NULL;elset=new BT;t-data=x;printf(ntt请输入%c结点的左子结点：,t-data);t-lchild=CreateTree();printf(ntt请输入%c结点的右子结点：,t-data);t-rchild=CreateTree();return t;void Preorder(BT *T)if(T)printf(%3c,T-data);Preorder(T-lchild);Preorder(T-rchild);void Inorder(BT *T)if(T)Inorder(T-lchild);printf(%3c,T-data);I

11、norder(T-rchild);void Postorder(BT *T)if(T)Postorder(T-lchild);Postorder(T-rchild);printf(%3c,T-data);void Levelorder(BT *T)int i,j;BT *q100,*p;p=T;if(p!=NULL)i=1;qi=p;j=2;while(i!=j)p=qi;printf(%3c,p-data);if(p-lchild!=NULL)qj=p-lchild;j+;if(p-rchild!=NULL)qj=p-rchild;j+;i+;void Leafnum(BT *T)if(T)

12、if(T-lchild=NULL&T-rchild=NULL)count+;Leafnum(T-lchild);Leafnum(T-rchild);void Nodenum(BT *T)if(T)count+;Nodenum(T-lchild);Nodenum(T-rchild);int TreeDepth(BT *T)int ldep,rdep;if(T=NULL)return 0;elseldep=TreeDepth(T-lchild);rdep=TreeDepth(T-rchild);if(ldeprdep)return ldep+1;elsereturn rdep+1;void Sho

13、wTree(BT *T)BT *stackTREEMAX,*p;int levelTREEMAX2,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+;stacktop=p-rchild;leveltop0=n+width;leveltop1=2;if(p-lchild!=NULL)top+;stacktop=p-lchild;le

14、veltop0=n+width;leveltop1=1;5程序运行6实验小结本章要求我们掌握的是二叉树的特点、存储方式、创建、显示、遍历以及节点数等计算方法。这个实验要求设计的是一颗二叉树，要求能用凹入法显示二叉树的结构，能读出前序遍历、中序遍历、后序遍历和层次遍历，以及会求解叶节点数、总节点数和树的深度。在输入程序的时候有些错误，但在编译和构建的时候都改正了，执行起来很方便。程序中在后面注释的帮助下也能知道相应程序的作用，结合上课听到的知识更容易理解了，这对我是一个不小的帮助。当然，在编译时发现错误的时候，改正也能帮我巩固记忆，让我知道什么地方错了，也能更好的学习并记住，争取以后不会再犯同样的错误。总的来说，本次实验还是成功的。