《实验二叉树子系统》由会员分享，可在线阅读，更多相关《实验二叉树子系统（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 结点的右子结点
