《实验二叉树子系统》由会员分享,可在线阅读,更多相关《实验二叉树子系统(14页珍藏版)》请在金锄头文库上搜索。
1、验证性实验 7:二叉树子系统班级学号 bx100526 姓名 王静波 成绩 1实验目的 (1)掌握二叉树的特点及其存储的方式。 (2)掌握二叉树的创建和显示方法。 (3)复习二叉树遍历的概念,掌握二叉树遍历的基本方法 (4)掌握求二叉树的叶结点数、总结点数和深度等基本算法。2实验内容 (1)按屏幕提示用前序方法建立一棵二叉树,并能按凹入法显示二叉树结构。 (2)编写前序遍历、中序遍历、后序遍历、层次遍历程序。 (3)编写求二叉树的叶结点数、总结点数和深度的程序。 (4)设计一个选择式菜单,以菜单方式选择下列操作。二 叉 树 子 系 统*“); * 1-建 二 叉 树 *“); * 2-凹 入
2、显 示 *“); * 3-先 序 遍 历 *“); * 4-中 序 遍 历 *“); * 5-后 序 遍 历 *“); * 6-层 次 遍 历 *“); * 7-求 叶 子 数 *“); * 8-求 结 点 数 *“); * 9-求 树 深 度 *“); * 0-返 回 *“);*“); 请选择菜单号(0-9):3实验步骤: (1)输入并调试程序;(2)按下图建立二叉树;abcdef二 叉 树 子 系 统* 1-建 二 叉 树 * 2-凹 入 显 示 * 3-先 序 遍 历 * 4-中 序 遍 历 * 5-后 序 遍 历 * 6-层 次 遍 历 * 7-求 叶 子 数 * 8-求 结 点 数
3、* 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-求 叶 子 数 * 8-求 结 点 数 * 9-求 树 深 度 *
5、 0-返 回 *请选择菜单号:3 该二叉树的先序遍历序列为:a b d c e f4实验程序 #include #define TREEMAX 100 typedef struct BT char 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); void Nodenum(BT *T)
6、; 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“, getchar(); printf(“n“); switch(ch2) case 1:printf(“ntt 请按先序序列输入二叉树的结点:n“);printf(“ntt 说明:输入结点(0表示后继结点为空)后按回车 .n“);printf(“ntt 请输入根结点: “);T=Cre
8、ateTree();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; case6:printf(“ntt 该二叉树的层次遍历序列为:“); Levelorder(T);break;case7:count=0
9、;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键继续,按任意键返回主菜单!n“);a=getchar();if(a!=xA) getchar();ch1=n; BT *CreateTree() BT *t;char x;scanf(“%c“,getchar();if(x=0)t=NULL;else t=new BT; t-data=x; printf(“ntt 请输入%c 结点的左子结点:“,t-data); t-lchild=CreateTree(); printf(“ntt 请输入%c 结点的右子结点