《二叉树基本操作演示程序的设计与实现》由会员分享，可在线阅读，更多相关《二叉树基本操作演示程序的设计与实现（9页珍藏版）》请在金锄头文库上搜索。
1、.二叉树根本操作演示程序的设计与实现二叉树根本操作演示程序的设计与实现2021 级电器信息类 X 班XX学号注意：文档以 word 格式提供，文件名起名规那么：学号+XX+实验报告名称一、需求分析1、创立二叉树。按照用户需要的二叉树，构建二叉树。2、将创立的二叉树，以树状形式输出。3、分别以先序、中序、后序三种方式遍历访问二叉树。4、输出二叉树的叶子结点及叶子结点的个数。5、输出二叉树的高度。6、将创立的二叉树，以括号形式输出。二、概要设计为了实现以上功能，可以从三个方面着手设计。1、主界面设计为了实现二叉树相关操作功能的管理， 设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用
2、户使用本程序。本系统主控菜单运行界面如图1 所示。首先请输入二叉树结点序列：请按菜单提示操作：-欢迎使用二叉树根本操作程序-菜单项选择择1. 树状输出二叉树2. 先序遍历二叉树3. 中序遍历二叉树4. 后序遍历二叉树5. 输出叶子结点6. 输出叶子结点个数7. 输出二叉树的深度8. 括号形式输出二叉树9. 退出-图 1 二叉树根本操作程序主菜单2、存储构造设计本程序采用二叉链式存储类型(BiTNode)存储二叉树的结点信息。二叉树的链表中的结点至少包含 3 个域：数据域(data)、左孩子指针域(lchild)、右孩子指针域(rchild)。3、系统功能设计本程序除了完成二叉树的创立功能外还设
3、置了9 个子功能菜单。 由于这 9 个子功能都是建立在二叉树的构造上的，所以二叉树的创立由主函数main()实现。9 个子功能的设计描述如下：树状输出二叉树。 树状输出二叉树由函数TranslevelPrint()实现。 当用户选择此功能时，系统即以树状的形式输出用户所创立的二叉树。先序遍历二叉树。由函数 Preorder()实现。该功能按照先序遍历访问二叉树的方法输出先序序列。中序遍历二叉树。由函数 Inorder()实现。该功能按照中序遍历访问二叉树的方法输出中序序列。后序遍历二叉树。由函数Postorder()实现。该功能按照后序遍历访问二叉树的方法输出后序序列。输出叶子结点。该功能采用
4、先序遍历二叉树的方法依次输出叶子结点。由函数Preorderleaf()实现。.v.输出叶子结点个数。 该功能计算并输出二叉树中叶子结点的个数， 由 LeafCount()实现。采用递归算法计算二叉树中叶子结点的个数， 算法思想是：当二叉树为空树时，叶子结点总数为 0；当二叉树只有 1 个结点时，叶子结点总数为 1；否那么，叶子结点个数等于左右子树叶子结点数之和。输出二叉树的深度。该功能输出二叉树的深度，由函数 PostorderDepth()实现，采用后序遍历的递归算法求二叉树的深度。括号形式输出二叉树。以括号形式输出二叉树由函数，由函数output()实现。当用户选择此功能时，系统即以括号
5、形式输出二叉树。退出。由 exit(0)函数实现。三、模块设计1、模块设计本程序包含三个模块，主程序模块、建立二叉树模块和工作区选择模块。其调用关系如图 2 所示。主程序模块建立二叉树模块工作区选择模块图 2 模块调用示意图2、系统子程序用功能设计本系统共设置 12 个子程序，各子程序的函数名及功能说明如下：void CreateBiTree(BiTree &T)/先序建立二叉树void TranslevelPrint(BiTree T)/树形打印二叉树void Visit(char ch) /输出结点void Preorder(BiTree T)/先序遍历二叉树void Inorder(Bi
6、Tree T)/中序遍历二叉树void Postorder(BiTree T)/后序遍历二叉树void PreorderLeaf(BiTree T)/输出叶子结点int LeafCount(BiTree T)/输出叶子结点的个数int PostorderDepth(BiTree T)/输出二叉树的深度void output(BiTree T)/以括号形式输出二叉树void mainwork()/主工作函数，操作区用户界面void main()/主函数。创立二叉树，调用工作区模块函数3、函数主要调用关系图本系统 12 个子程序之间的主要调用关系如图3 所示。图中数字是各函数的编号。图 3 系统函
7、数调用关系图四、详细设计1、数据类型定义typedef struct BiTNode/定义二叉树结点构造char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;.v.2、系统主要子程序详细设计主函数模块主函数。创立二叉树，调用工作区模块函数。void main() cout首先请输入二叉树结点序列： n;CreateBiTree(T);coutch;if(ch=*)T=NULL;elseT=new BiTNode;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);用户工作区模
8、块主工作函数，操作区用户界面设计。void mainwork() int yourchoice;coutn-欢迎使用二叉树根本操作程序-n;coutn菜单项选择择nn;cout1. 树状输出二叉树2. 先序遍历二叉树n;cout3. 中序遍历二叉树4. 后序遍历二叉树n;cout5. 输出叶子结点6. 输出叶子结点个数n;cout7. 输出二叉树的深度8. 括号形式输出二叉树 n;cout9. 退出n;coutn-n;coutyourchoice;while(!(yourchoice=1|yourchoice=2|yourchoice=4|yourchoice=5|yourchoice=6|y
9、ourchoice=7|yourchoice=8|yourchoice=9) coutyourchoice;while(1) switch(yourchoice)case 1:cout树的形状为：; TranslevelPrint(T);break;case 2:cout先序遍历为：; Preorder(T);break;.v.case 3:cout中序遍历为：; Inorder(T);break;case 4:cout后序遍历为：; Postorder(T);break;case 5:cout叶子结点为：; PreorderLeaf(T);break;case 6:cout叶子结点个数为：L
10、eafCount(T);break;case 7:cout二叉树的深度为：PostorderDepth(T);break;case 8:cout括号形式输出二叉树为:;output(T);break;case 9:system(cls); exit(0); break;default: break;coutn 按任意键继续：; getch();system(cls);coutn-欢迎使用二叉树根本操作程序-n;coutn菜 单 项 选 择 择nn;cout1. 树状输出二叉树2. 先序遍历二叉树n;cout3. 中序遍历二叉树4. 后序遍历二叉树n;cout5. 输出叶子结点6. 输出叶子结点
11、个数n;cout7. 输出二叉树的深度8. 括号形式输出二叉树 n;cout9. 退出n;coutn-n;coutyourchoice;/endwhile(1)/endmainwork五、测试结果根据先根结点，按照从上到下，从左到右的次序依次先根遍历的方法， 分别输入二叉树的结点序列*号表示该结点为空 。例如，输入ABD*E*CH*，程序运行得到如图 1所示的开场界面。各子功能测试运行结果如下。1、树状输出二叉树在主菜单下，用户输入 1 并回车，运行结果如图 4 所示。图 4 按树形输出所创立的二叉树2、先序遍历二叉树在主菜单下，用户输入 2 并回车，运行结果如图 5 所示。图 5 输出二叉树
12、的先序遍历序列3、中序遍历二叉树在主菜单下，用户输入 3 并回车，运行结果如图 6 所示。4、后序遍历二叉树在主菜单下，用户输入 4 并回车，运行结果如图 7 所示。图 6 输出二叉树的中序遍历序列图 7 输出二叉树的后序遍历序列5、输出叶子结点在主菜单下，用户输入 5 并回车，运行结果如图 8 所示。6、输出叶子结点个数在主菜单下，用户输入 6 并回车，运行结果如图 9 所示。.v.图 8 输出二叉树的叶子结点图 9 输出二叉树的叶子结点个数7、输出二叉树的深度在主菜单下，用户输入 7 并回车，运行结果如图 10 所示。8、括号形式输出二叉树在主菜单下，用户输入 8 并回车，运行结果如图 1
13、1 所示。图 10 输出二叉树的深度图 11 以括号形式输出二叉树9、退出在主菜单下，用户输入 9 并回车，即退出二叉树根本操作程序。六、用户使用说明1、本程序执行文件为二叉树的根本操作演示.exe。2、进入本程序后，首先按照提示输入二叉树的结点，如按以下次序顺序读入字符ABD*E*CH*。3、随即显示系统主菜单界面，用户可在该界面下输入各功能前对应的数字并按回车，执行相应命令。七、实验体会略八、源程序清单/二叉树根本操作演示程序的设计与实现/二叉树的根本操作演示.CPP*include *include stdlib.h*include conio.h*include math.h*defi
14、ne MaxSize 100*define NLAYER 4typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;/1.建立二叉树void CreateBiTree(BiTree &T)/先序建立二叉树 char ch;cinch;if(ch=*)T=NULL;elseT=new BiTNode;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);/2.树形打印二叉树void TranslevelPrint(BiT
15、ree T).v. /本算法实现二叉树按层打印struct node BiTree vecMaxSize;/存放树结点int layerMaxSize;/结点所在的层int locateMaxSize;/打印结点的位置int front,rear;q;/定义队列 qint i,j=1,k=0,nLocate;q.front=q.rear=0;/初始化队列 q 队头、队尾coutn ;q.vecq.rear=T;/二叉树的根结点入队q.layerq.rear=1;q.locateq.rear=20;q.rear=q.rear+1;while(q.frontq.rear) T=q.vecq.fro
16、nt;i=q.layerq.front;nLocate=q.locateq.front;if(ji)/进层打印时换行 coutnn;j=j+1;k=0;while(k+nLocate)cout;while(k+nLocate-1) cout;/结点深度控制横向位置coutdata;q.front=q.front+1;if(T-lchild!=NULL)/存在左子树，将左子树的根结点入队列 q.vecq.rear=T-lchild;q.layerq.rear=i+1;q.locateq.rear=int(nLocate-pow(2,NLAYER-i-1);q.rear=q.rear+1;if(T
17、-rchild!=NULL)/存在右子树，将右子树的根结点入队列 q.vecq.rear=T-rchild;q.layerq.rear=i+1;q.locateq.rear=int(nLocate+pow(2,NLAYER-i-1);q.rear=q.rear+1;/3.输出结点void Visit(char ch)coutdata);/访问根结点Preorder(T-lchild);/先序遍历左子树Preorder(T-rchild);/先序遍历右子树/5.中序遍历二叉树void Inorder(BiTree T)/中序遍历二叉树，T 为指向二叉树或某一子树根结点的指针if(T!=NULL)
18、Inorder(T-lchild);/中序遍历左子树Visit(T-data);/访问根结点Inorder(T-rchild);/中序遍历右子树/6.后序遍历二叉树void Postorder(BiTree T)/后序遍历二叉树，T 为指向二叉树或某一子树根结点的指针if(T!=NULL)Postorder(T-lchild);/后序遍历左子树Postorder(T-rchild);/后序遍历右子树Visit(T-data);/访问根结点/7.输出叶子结点void PreorderLeaf(BiTree T)/先序遍历二叉树并输出叶子结点，T 为指向二叉树根结点的指针if(T!=NULL)if
19、(T-lchild=NULL&T-rchild=NULL)Visit(T-data);/访问根结点PreorderLeaf(T-lchild);/先序遍历左子树PreorderLeaf(T-rchild);/先序遍历右子树/8.输出叶子结点的个数int LeafCount(BiTree T) int LeafNum;.v.if(T=NULL) LeafNum=0;else if(T-lchild=NULL)&(T-rchild=NULL) LeafNum=1;else LeafNum=LeafCount(T-lchild)+LeafCount(T-rchild);return LeafNum;
20、/9.输出二叉树的深度int PostorderDepth(BiTree T) /后序遍历求二叉树深度的递归算法int hl,hr,max;if(T!=NULL)hl=PostorderDepth(T-lchild);/求左子树的深度hr=PostorderDepth(T-rchild);/求右子树的深度max=hlhrhl:hr;/得到左右子树深度较大者return (max+1);/返回树的深度else return 0;/空树返回 0/10. 以括号形式输出二叉树void output(BiTree T) if(T!=NULL) coutdata;if(T-lchild!=NULL|T-
21、rchild!=NULL)coutlchild);if(T-rchild!=NULL)coutrchild);cout);/11.主工作函数，操作区用户界面void mainwork() int yourchoice;coutn-欢迎使用二叉树根本操作程序-n;coutn菜单项选择择nn;cout1. 树状输出二叉树2. 先序遍历二叉树n;cout3. 中序遍历二叉树4. 后序遍历二叉树n;cout5. 输出叶子结点6. 输出叶子结点个数n;cout7. 输出二叉树的深度8. 括号形式输出二叉树 n;cout9. 退出n;coutn-n;coutyourchoice;.v.while(!(yo
22、urchoice=1|yourchoice=2|yourchoice=4|yourchoice=5|yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) coutyourchoice;while(1) switch(yourchoice)case 1:cout树的形状为：; TranslevelPrint(T);break;case 2:cout先序遍历为：; Preorder(T);break;case 3:cout中序遍历为：; Inorder(T);break;case 4:cout后序遍历为：; Postorder(T);break;
23、case 5:cout叶子结点为：; PreorderLeaf(T);break;case 6:cout叶子结点个数为：LeafCount(T);break;case 7:cout二叉树的深度为：PostorderDepth(T);break;case 8:cout括号形式输出二叉树为:;output(T);break;case 9:system(cls); exit(0); break;default: break;coutn 按任意键继续：; getch();system(cls);coutn-欢迎使用二叉树根本操作程序-n;coutn菜 单 项 选 择 择nn;cout1. 树状输出二叉树2. 先序遍历二叉树n;cout3. 中序遍历二叉树4. 后序遍历二叉树n;cout5. 输出叶子结点6. 输出叶子结点个数n;cout7. 输出二叉树的深度8. 括号形式输出二叉树 n;cout9. 退出n;coutn-n;coutyourchoice;/endwhile(1)/endmainwork/12.主函数void main() cout首先请输入二叉树结点序列： n;CreateBiTree(T);cout请按菜单提示操作：n;mainwork();.v.
