二叉树基本操作演示程序的设计与实现

二叉树基本操作演示程序的设计与实现2012级电器信息类X班（姓名）（学号）注意：文档以word格式提供，文件名起名规则：学号+姓名+实验报告名称一、需求分析1、创建二叉树。按照用户需要的二叉树，构建二叉树。2、将创建的二叉树，以树状形式输出。3、分别以先序、中序、后序三种方式遍历访问二叉树。4、输出二叉树的叶子结点及叶子结点的个数。5、输出二叉树的高度。6、将创建的二叉树，以括号形式输出。二、概要设计为了实现以上功能，可以从三个方面着手设计。1、主界面设计为了实现二叉树相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如图1所示。首先请输入二叉树结点序列：请按菜单提示操作：----------------------------欢迎使用二叉树基本操作程序-------------------------------菜单选择1.树状输出二叉树2.先序遍历二叉树3.中序遍历二叉树4.后序遍历二叉树5.输出叶子结点6.输出叶子结点个数7.输出二叉树的深度8.括号形式输出二叉树9.退出--------------------------------------------------------------------------------------------------图1二叉树基本操作程序主菜单2、存储结构设计本程序采用二叉链式存储类型(BiTNode)存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域(data)、左孩子指针域(lchild)、右孩子指针域(rchild)。3、系统功能设计本程序除了完成二叉树的创建功能外还设置了9个子功能菜单。由于这9个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main()实现。9个子功能的设计描述如下：⑴树状输出二叉树。树状输出二叉树由函数TranslevelPrint()实现。当用户选择此功能时，系统即以树状的形式输出用户所创建的二叉树。⑵先序遍历二叉树。由函数Preorder()实现。该功能按照先序遍历访问二叉树的方法输出先序序列。⑶中序遍历二叉树。由函数Inorder()实现。该功能按照中序遍历访问二叉树的方法输出中序序列。⑷后序遍历二叉树。由函数Postorder()实现。该功能按照后序遍历访问二叉树的方法输出后序序列。⑸输出叶子结点。该功能采用先序遍历二叉树的方法依次输出叶子结点。由函数Preorderleaf()实现。⑹输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount()实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有1个结点时，叶子结点总数为1；否则，叶子结点个数等于左右子树叶子结点数之和。⑺输出二叉树的深度。该功能输出二叉树的深度，由函数PostorderDepth()实现，采用后序遍历的递归算法求二叉树的深度。⑻括号形式输出二叉树。以括号形式输出二叉树由函数，由函数output()实现。当用户选择此功能时，系统即以括号形式输出二叉树。⑼退出。由exit(0)函数实现。三、模块设计1、模块设计本程序包含三个模块，主程序模块、建立二叉树模块和工作区选择模块。其调用关系如图2所示。图2模块调用示意图2、系统子程序用功能设计本系统共设置12个子程序，各子程序的函数名及功能说明如下：⑴voidCreateBiTree(BiTree&T)//先序建立二叉树⑵voidTranslevelPrint(BiTreeT)//树形打印二叉树⑶voidVisit(charch)//输出结点⑷voidPreorder(BiTreeT)//先序遍历二叉树⑸voidInorder(BiTreeT)//中序遍历二叉树⑹voidPostorder(BiTreeT)//后序遍历二叉树⑺voidPreorderLeaf(BiTreeT)//输出叶子结点⑻intLeafCount(BiTreeT)//输出叶子结点的个数⑼intPostorderDepth(BiTreeT)//输出二叉树的深度⑽voidoutput(BiTreeT)//以括号形式输出二叉树⑾voidmainwork()//主工作函数，操作区用户界面⑿voidmain()//主函数。创建二叉树，调用工作区模块函数3、函数主要调用关系图本系统12个子程序之间的主要调用关系如图3所示。图中数字是各函数的编号。主程序模块建立二叉树模块工作区选择模块图3系统函数调用关系图四、详细设计1、数据类型定义typedefstructBiTNode//定义二叉树结点结构{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2、系统主要子程序详细设计⑴主函数模块主函数。创建二叉树，调用工作区模块函数。voidmain(){cout首先请输入二叉树结点序列：\n;CreateBiTree(T);cout请按菜单提示操作：\n;mainwork();}⑵建立二叉树模块voidCreateBiTree(BiTree&T)//先序建立二叉树{charch;cinch;if(ch=='#')T=NULL;else{T=newBiTNode;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}}⑶用户工作区模块主工作函数，操作区用户界面设计。voidmainwork(){intyourchoice;cout\n---------------欢迎使用二叉树基本操作程序-----------------\n;cout\n菜单选择\n\n;cout1.树状输出二叉树2.先序遍历二叉树\n;cout3.中序遍历二叉树4.后序遍历二叉树\n;cout5.输出叶子结点6.输出叶子结点个数\n;cout7.输出二叉树的深度8.括号形式输出二叉树\n;cout9.退出\n;cout\n----------------------------------------------------------\n;cout请输入你的选择：;cinyourchoice;while(!(yourchoice==1||yourchoice==2||yourchoice==4||yourchoice==5||yourchoice==6||yourchoice==7||yourchoice==8||yourchoice==9)){cout输入不正确，请重新输入\n;cinyourchoice;}while(1){switch(yourchoice){case1:cout树的形状为：;TranslevelPrint(T);break;case2:cout先序遍历为：;Preorder(T);break;case3:cout中序遍历为：;Inorder(T);break;case4:cout后序遍历为：;Postorder(T);break;case5:cout叶子结点为：;PreorderLeaf(T);break;case6:cout叶子结点个数为：LeafCount(T);break;case7:cout二叉树的深度为：PostorderDepth(T);break;case8:cout括号形式输出二叉树为:;output(T);break;case9:system(cls);exit(0);break;default:break;}cout\n按任意键继续：;getch();system(cls);cout\n---------------欢迎使用二叉树基本操作程序-----------------\n;cout\n菜单选择\n\n;cout1.树状输出二叉树2.先序遍历二叉树\n;cout3.中序遍历二叉树4.后序遍历二叉树\n;cout5.输出叶子结点6.输出叶子结点个数\n;cout7.输出二叉树的深度8.括号形式输出二叉树\n;cout9.退出\n;cout\n----------------------------------------------------------\n;cout请输入你的选择：;cinyourchoice;}//endwhile(1)}//endmainwork五、测试结果根据先根结点，按照从上到下，从左到右的次序依次先根遍历的方法，分别输入二叉树的结点序列（#号表示该结点为空）。例如，输入“ABD##E##CH###”，程序运行得到如图1所示的开始界面。各子功能测试运行结果如下。1、树状输出二叉树在主菜单下，用户输入1并回车，运行结果如图4所示。图4按树形输出所创建的二叉树2、先序遍历二叉树在主菜单下，用户输入2并回车，运行结果如图5所示。图5输出二叉树的先序遍历序列3、中序遍历二叉树在主菜单下，用户输入3并回车，运行结果如图6所示。4、后序遍历二叉树在主菜单下，用户输入4并回车，运行结果如图7所示。图6输出二叉树的中序遍历序列图7输出二叉树的后序遍历序列5、输出叶子结点在主菜单下，用户输入5并回车，运行结果如图8所示。6、输出叶子结点个数在主菜单下，用户输入6并回车，运行结果如图9所示。图8输出二叉树的叶子结点图9输出二叉树的叶子结点个数7、输出二叉树的深度在主菜单下，用户输入7并回车，运行结果如图10所示。8、括号形式输出二叉树在主菜单下，用户输入8并回车，运行结果如图11所示。图10输出二叉树的深度图11以括号形式输出二叉树9、退出在主菜单下，用户输入9并回车，即退出“二叉树基本操作程序”。六、用户使用说明1、本程序执行文件为“二叉树的基本操作演示.exe”。2、进入本程序后，首先按照提示输入二叉树的结点，如按下列次序顺序读入字符ABD##E##CH###。3、随即显示系统主菜单界面，用户可在该界面下输入各功能前对应的数字并按回车，执行相应命令。七、实验体会（略）八、源程序清单//二叉树基本操作演示程序的设计与实现//二叉树的基本操作演示.CPP#includeiostream.h#includestdlib.h#includeconio.h#includemath.h#defineMaxSize100#defineNLAYER4typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeT;//1.建立二叉树voidCreateBiTree(BiTree&T)//先序建立二叉树{charch;cinch;if(ch=='#')T=NULL;else{T=newBiTNode;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}}//2.树形打印二叉树voidTranslevelPrint(BiTreeT){//本算法实现二叉树按层打印structnode{BiTreevec[MaxSize];//存放树结点intlayer[MaxSize];//结点所在的层intlocate[MaxSize];//打印结点的位置intfront,rear;}q;//定义队列qinti,j=1,k=0,nLocate;q.front=q.rear=0;//初始化队列q队头、队尾cout\n;q.vec[q.rear]=T;//二叉树的根结点入队q.layer[q.rear]=1;q.locate[q.rear]=20;q.rear=q.rear+1;while(q.frontq.rear){T=q.vec[q.front];i=q.layer[q.front];nLocate=q.locate[q.front];if(ji)/