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

-验证性实验7：二叉树子系统班级学号 BX100420 姓名 施程程 成绩 1实验目的（1）掌握二叉树的特点及其存储的方式。（2）掌握二叉树的创建和显示方法。（3）复习二叉树遍历的概念，掌握二叉树遍历的基本方法（4）掌握求二叉树的叶结点数、总结点数和深度等基本算法。2实验内容（1）按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。（2）编写前序遍历、中序遍历、后序遍历、层次遍历程序。（3）编写求二叉树的叶结点数、总结点数和深度的程序。（4）设计一个选择式菜单，以菜单方式选择下列操作。 二 叉 树 子 系 统*");* 1-建 二 叉 树 *");* 2-凹 入 显 示 *");* 3-先 序 遍 历 *");* 4-中 序 遍 历 *");* 5-后 序 遍 历 *");* 6-层 次 遍 历 *");* 7-求 叶 子 数 *");* 8-求 结 点 数 *");* 9-求 树 深 度 *");* 0-返 回 *");*");请选择菜单号（0-9）：3实验步骤：（1）输入并调试程序；（2）按下图建立二叉树；abcdef 二 叉 树 子 系 统 * * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * * 7-求 叶 子 数 * * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * * 请选择菜单号：1<CR>请输入按先序建立二叉树的结点序列：说明：'0'代表后继结点为空，请逐个输入，按回车键输入下一结点。请输入根结点：a<CR>请输入a结点的左子结点：b<CR>请输入b结点的左子结点：d<CR>请输入d结点的左子结点：0<CR>请输入d结点的右子结点：0<CR>请输入b结点的右子结点：0<CR>请输入a结点的右子结点：c<CR>请输入c结点的左子结点：e<CR>请输入e结点的左子结点：0<CR>请输入e结点的右子结点：0<CR>请输入c结点的右子结点：f<CR>请输入f结点的左子结点：0<CR>请输入f结点的右子结点：0<CR>（3）检查凹入法显示的二叉树是否正确； 二 叉 树 子 系 统 * * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * * 7-求 叶 子 数 * * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * * 请选择菜单号：2<CR>凹入表示法： a b d c e f 按回车键返回主菜单! <CR>（4）检查其他算法的正确性举例： 二 叉 树 子 系 统 * * 1-建 二 叉 树 * * 2-凹 入 显 示 * * 3-先 序 遍 历 * * 4-中 序 遍 历 * * 5-后 序 遍 历 * * 6-层 次 遍 历 * * 7-求 叶 子 数 * * 8-求 结 点 数 * * 9-求 树 深 度 * * 0-返 回 * * 请选择菜单号：3<CR>该二叉树的先序遍历序列为：a b d c e f4实验程序 #include<stdio.h>#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);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-层 次 遍 历 *");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("ntt二叉树成功建立！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);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();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);Inorder(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)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(ldep>rdep)return ldep+1;elsereturn rdep+1;void ShowTree(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(top>0)p=stacktop;n=leveltop0;for(i=1;i<=n;i+)printf(" ");printf("%c",p->data);for(i=n+1;i<30;i+=2)printf("");printf("ntt");top-;if(p->rchild!=NULL)top+;stacktop=p->rchild;leveltop0=n+width;leveltop1=2;if(p->lchild!=NULL)top+;stacktop=p->lchild;leveltop0=n+width;leveltop1=1;5程序运行 6实验小结本章要求我们掌握的是二叉树的特点、存储方式、创建、显示、遍历以及节点数等计算方法。这个实验要求设计的是一颗二叉树，要求能用凹入法显示二叉树的结构，能读出前序遍历、中序遍历、后序遍历和层次遍历，以及会求解叶节点数、总节点数和树的深度。在输入程序的时候有些错误，但在编译和构建的时候都改正了，执行起来很方便。程序中在后面注释的帮助下也能知道相应程序的作用，结合上课听到的知识更容易理解了，这对我是一个不小的帮助。当然，在编译时发现错误的时候，改正也能帮我巩固记忆，让我知道什么地方错了，也能更好的学习并记住，争取以后不会再犯同样的错误。总的来说，本次实验还是成功的。-第 15 页-