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

1、二叉树基本操作演示程序的设计与实现2012级电器信息类X班 （姓名） （学号）注意：文档以word格式提供，文件名起名规则：学号+姓名+实验报告名称一、需求分析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、系统功能设计本程序除了完成二叉树的创建功能外还设置了9个子功能菜单。由于

3、这9个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main()实现。9个子功能的设计描述如下：树状输出二叉树。树状输出二叉树由函数TranslevelPrint()实现。当用户选择此功能时，系统即以树状的形式输出用户所创建的二叉树。先序遍历二叉树。由函数Preorder()实现。该功能按照先序遍历访问二叉树的方法输出先序序列。中序遍历二叉树。由函数Inorder()实现。该功能按照中序遍历访问二叉树的方法输出中序序列。后序遍历二叉树。由函数Postorder()实现。该功能按照后序遍历访问二叉树的方法输出后序序列。输出叶子结点。该功能采用先序遍历二叉树的方法依次输出叶子结点。由函

4、数Preorderleaf()实现。输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount()实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有1个结点时，叶子结点总数为1；否则，叶子结点个数等于左右子树叶子结点数之和。输出二叉树的深度。该功能输出二叉树的深度，由函数PostorderDepth()实现，采用后序遍历的递归算法求二叉树的深度。括号形式输出二叉树。以括号形式输出二叉树由函数，由函数output()实现。当用户选择此功能时，系统即以括号形式输出二叉树。退出。由exit(0)函数实现。三、模块设计1、模块

5、设计本程序包含三个模块，主程序模块、建立二叉树模块和工作区选择模块。其调用关系如图2所示。主程序模块建立二叉树模块工作区选择模块图2 模块调用示意图2、系统子程序用功能设计本系统共设置12个子程序，各子程序的函数名及功能说明如下：void CreateBiTree(BiTree &T) /先序建立二叉树void TranslevelPrint(BiTree T) /树形打印二叉树void Visit(char ch) /输出结点void Preorder(BiTree T) /先序遍历二叉树void Inorder(BiTree T) /中序遍历二叉树void Postorder(Bi

6、Tree 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系统函数调用关系图四、详细设计1、数据类型定义typedef st

7、ruct BiTNode /定义二叉树结点结构 char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2、系统主要子程序详细设计主函数模块主函数。创建二叉树，调用工作区模块函数。void main() cout<<"首先请输入二叉树结点序列： n" CreateBiTree(T); cout<<"请按菜单提示操作：n" mainwork();建立二叉树模块void CreateBiTree(BiTree &T)/先序建立二叉树 char ch; cin>&

8、gt;ch; if(ch='#') T=NULL; else T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); 用户工作区模块主工作函数，操作区用户界面设计。void mainwork() int yourchoice; cout<<"n-欢迎使用二叉树基本操作程序-n" cout<<"n 菜单选择 nn" cout<<" 1. 树状输出二叉树 2. 先序遍历二叉树 n&q

9、uot; cout<<" 3. 中序遍历二叉树 4. 后序遍历二叉树 n" cout<<" 5. 输出叶子结点 6. 输出叶子结点个数 n" cout<<" 7. 输出二叉树的深度 8. 括号形式输出二叉树 n" cout<<" 9. 退出 n" cout<<"n-n" cout<<"请输入你的选择： " cin>>yourchoice; while(!(yourchoice=1|yourch

10、oice=2|yourchoice=4|yourchoice=5| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) cout<<"输入不正确，请重新输入n" cin>>yourchoice; while(1) switch(yourchoice) case 1:cout<<"树的形状为：" TranslevelPrint(T);break; case 2:cout<<"先序遍历为：" Preorder(T);break; case

11、 3:cout<<"中序遍历为：" Inorder(T);break; case 4:cout<<"后序遍历为：" Postorder(T);break; case 5:cout<<"叶子结点为：" PreorderLeaf(T);break; case 6:cout<<"叶子结点个数为："<<LeafCount(T);break; case 7:cout<<"二叉树的深度为："<<PostorderDepth(

12、T);break; case 8:cout<<"括号形式输出二叉树为:"output(T);break; case 9:system("cls"); exit(0); break; default: break; cout<<"n按任意键继续：" getch(); system("cls"); cout<<"n-欢迎使用二叉树基本操作程序-n" cout<<"n 菜单选择 nn" cout<<" 1. 树状

13、输出二叉树 2. 先序遍历二叉树 n" cout<<" 3. 中序遍历二叉树 4. 后序遍历二叉树 n" cout<<" 5. 输出叶子结点 6. 输出叶子结点个数 n" cout<<" 7. 输出二叉树的深度 8. 括号形式输出二叉树 n" cout<<" 9. 退出 n" cout<<"n-n" cout<<"请输入你的选择： " cin>>yourchoice; /endwhi

14、le(1)/endmainwork五、测试结果根据先根结点，按照从上到下，从左到右的次序依次先根遍历的方法，分别输入二叉树的结点序列（#号表示该结点为空）。例如，输入“ABD#E#CH#”，程序运行得到如图1所示的开始界面。各子功能测试运行结果如下。1、树状输出二叉树在主菜单下，用户输入1并回车，运行结果如图4所示。 图4 按树形输出所创建的二叉树2、先序遍历二叉树在主菜单下，用户输入2并回车，运行结果如图5所示。图5 输出二叉树的先序遍历序列3、中序遍历二叉树在主菜单下，用户输入3并回车，运行结果如图6所示。4、后序遍历二叉树在主菜单下，用户输入4并回车，运行结果如图7所示。 图6 输出二叉

15、树的中序遍历序列 图7 输出二叉树的后序遍历序列5、输出叶子结点在主菜单下，用户输入5并回车，运行结果如图8所示。6、输出叶子结点个数在主菜单下，用户输入6并回车，运行结果如图9所示。 图8 输出二叉树的叶子结点 图9输出二叉树的叶子结点个数7、输出二叉树的深度在主菜单下，用户输入7并回车，运行结果如图10所示。8、括号形式输出二叉树在主菜单下，用户输入8并回车，运行结果如图11所示。 图10 输出二叉树的深度 图11 以括号形式输出二叉树9、退出在主菜单下，用户输入9并回车，即退出“二叉树基本操作程序”。六、用户使用说明1、本程序执行文件为“二叉树的基本操作演示.exe”。2、进入本程序后，

16、首先按照提示输入二叉树的结点，如按下列次序顺序读入字符ABD#E#CH#。 3、随即显示系统主菜单界面，用户可在该界面下输入各功能前对应的数字并按回车，执行相应命令。七、实验体会（略）八、源程序清单/二叉树基本操作演示程序的设计与实现/二叉树的基本操作演示.CPP#include <iostream.h>#include "stdlib.h"#include "conio.h"#include "math.h"#define MaxSize 100#define NLAYER 4typedef struct BiTNode

17、 char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;/1.建立二叉树void CreateBiTree(BiTree &T)/先序建立二叉树 char ch; cin>>ch; if(ch='#') T=NULL; else T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); /2.树形打印二叉树void TranslevelPrint(BiTree T)

18、/本算法实现二叉树按层打印 struct node BiTree vecMaxSize; /存放树结点 int layerMaxSize; /结点所在的层 int locateMaxSize; /打印结点的位置int front,rear; q; /定义队列q int i,j=1,k=0,nLocate; q.front=q.rear=0; /初始化队列q队头、队尾 cout<<"n " q.vecq.rear=T; /二叉树的根结点入队 q.layerq.rear=1; q.locateq.rear=20; q.rear=q.rear+1; while(q.f

19、ront<q.rear) T=q.vecq.front; i=q.layerq.front; nLocate=q.locateq.front; if(j<i) /进层打印时换行 cout<<"nn" j=j+1; k=0; while(k+<nLocate) cout<<" "while(k+<nLocate-1) cout<<" " /结点深度控制横向位置cout<<T->data;q.front=q.front+1;if(T->lchild!=NU

20、LL) /存在左子树，将左子树的根结点入队列 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->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(ch

21、ar ch) cout<<ch;/4.先序遍历二叉树void Preorder(BiTree T)/先序遍历二叉树，T为指向二叉树（或某一子树）根结点的指针 if(T!=NULL) Visit(T->data); /访问根结点 Preorder(T->lchild); /先序遍历左子树 Preorder(T->rchild); /先序遍历右子树 /5.中序遍历二叉树void Inorder(BiTree T)/中序遍历二叉树，T为指向二叉树（或某一子树）根结点的指针 if(T!=NULL) Inorder(T->lchild); /中序遍历左子树 Visit

22、(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)

23、 if(T->lchild=NULL&&T->rchild=NULL) Visit(T->data); /访问根结点 PreorderLeaf(T->lchild); /先序遍历左子树 PreorderLeaf(T->rchild); /先序遍历右子树 /8.输出叶子结点的个数int LeafCount(BiTree T) int LeafNum; if(T=NULL) LeafNum=0; else if(T->lchild=NULL)&&(T->rchild=NULL) LeafNum=1; else LeafNum

24、=LeafCount(T->lchild)+LeafCount(T->rchild); return LeafNum;/9.输出二叉树的深度int PostorderDepth(BiTree T) /后序遍历求二叉树深度的递归算法 int hl,hr,max; if(T!=NULL) hl=PostorderDepth(T->lchild); /求左子树的深度 hr=PostorderDepth(T->rchild); /求右子树的深度 max=hl>hr?hl:hr; /得到左右子树深度较大者 return (max+1); /返回树的深度 else retur

25、n 0; /空树返回0/10. 以括号形式输出二叉树void output(BiTree T) if(T!=NULL) cout<<T->data; if(T->lchild!=NULL|T->rchild!=NULL) cout<<"(" output(T->lchild); if(T->rchild!=NULL) cout<<"," output(T->rchild); cout<<")" /11.主工作函数，操作区用户界面void mainwor

26、k() int yourchoice; cout<<"n-欢迎使用二叉树基本操作程序-n" cout<<"n 菜单选择 nn" cout<<" 1. 树状输出二叉树 2. 先序遍历二叉树 n" cout<<" 3. 中序遍历二叉树 4. 后序遍历二叉树 n" cout<<" 5. 输出叶子结点 6. 输出叶子结点个数 n" cout<<" 7. 输出二叉树的深度 8. 括号形式输出二叉树 n" cout&

27、lt;<" 9. 退出 n" cout<<"n-n" cout<<"请输入你的选择： " cin>>yourchoice; while(!(yourchoice=1|yourchoice=2|yourchoice=4|yourchoice=5| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) cout<<"输入不正确，请重新输入n" cin>>yourchoice; 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; ca