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

《2022年二叉树基本操作演示程序的设计与实现 .pdf》由会员分享，可在线阅读，更多相关《2022年二叉树基本操作演示程序的设计与实现 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、名师归纳总结 - - - - - - -第 1 页，共 10 页输出叶子结点。该功能采用先序遍历二叉树的方法依次输出叶子结点。由函数Preorderleaf()实现。输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount() 实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有1 个结点时，叶子结点总数为1；否则，叶子结点个数等于左右子树叶子结点数之和。输出二叉树的深度。该功能输出二叉树的深度，由函数PostorderDepth()实现，采用后序遍历的递归算法求二叉树的深度。括号形式输出二叉树。以括号形式输出二叉树由

5、函数，由函数output()实现。当用户选择此功能时，系统即以括号形式输出二叉树。退出。由exit(0) 函数实现。三、模块设计1、模块设计本程序包含三个模块，主程序模块、建立二叉树模块和工作区选择模块。其调用关系如图 2 所示。图 2 模块调用示意图2、系统子程序用功能设计本系统共设置12 个子程序，各子程序的函数名及功能说明如下：void CreateBiTree(BiTree &T) /先序建立二叉树void TranslevelPrint(BiTree T) /树形打印二叉树void Visit(char ch) /输出结点void Preorder(BiTree T) /先序遍历二叉

6、树void Inorder(BiTree 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 个子程序之间的主要调用关系如图

7、3 所示。图中数字是各函数的编号。主程序模块建立二叉树模块工作区选择模块精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 10 页图 3 系统函数调用关系图四、详细设计1、数据类型定义typedef struct BiTNode /定义二叉树结点结构 char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 2、系统主要子程序详细设计主函数模块主函数。创建二叉树，调用工作区模块函数。void main() cout 首先请输入二叉树结点序列：n; CreateBiTree(T)

8、; coutch; if(ch=#) T=NULL; else T=new BiTNode; T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); 用户工作区模块精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 10 页主工作函数，操作区用户界面设计。void mainwork() int yourchoice; coutn-欢迎使用二叉树基本操作程序-n; coutn 菜单选择nn; cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4.

9、 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; while(!(yourchoice=1|yourchoice=2|yourchoice=4|yourchoice=5| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) coutyourchoice; while(1) switch(yourchoice) case 1:cout 树的形状为：; TranslevelPrin

10、t(T);break; case 2:cout先序遍历为： ; Preorder(T);break; case 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(T);break; case 8:cout括号形式输出二叉树为:;output(T);break; case

11、9:system(cls); exit(0); break; default: break; coutn 按任意键继续：; getch(); system(cls); coutn-欢迎使用二叉树基本操作程序-n; coutn 菜单选择nn; cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4. 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; /endwhile(1) 精选学习资料 - - -

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

13、，运行结果如图6 所示。4、后序遍历二叉树在主菜单下，用户输入4 并回车，运行结果如图7 所示。图 6 输出二叉树的中序遍历序列图 7 输出二叉树的后序遍历序列5、输出叶子结点在主菜单下，用户输入5 并回车，运行结果如图8 所示。6、输出叶子结点个数在主菜单下，用户输入6 并回车，运行结果如图9 所示。图 8 输出二叉树的叶子结点图 9 输出二叉树的叶子结点个数7、输出二叉树的深度在主菜单下，用户输入7 并回车，运行结果如图10 所示。8、括号形式输出二叉树在主菜单下，用户输入8 并回车，运行结果如图11 所示。图 10 输出二叉树的深度图 11 以括号形式输出二叉树9、退出在主菜单下，用户输

14、入9 并回车，即退出“ 二叉树基本操作程序” 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 10 页六、用户使用说明1、本程序执行文件为“二叉树的基本操作演示.exe” 。2、进入本程序后，首先按照提示输入二叉树的结点，如按下列次序顺序读入字符ABD#E#CH# 。3、随即显示系统主菜单界面，用户可在该界面下输入各功能前对应的数字并按回车，执行相应命令。七、实验体会（略）八、源程序清单/二叉树基本操作演示程序的设计与实现/二叉树的基本操作演示.CPP #include #include stdlib.h #include conio

15、.h #include math.h #define MaxSize 100 #define NLAYER 4 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; BiTree T; /1.建立二叉树void CreateBiTree(BiTree &T)/先序建立二叉树 char ch; cinch; if(ch=#) T=NULL; else T=new BiTNode; T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rch

16、ild); /2.树形打印二叉树void TranslevelPrint(BiTree T) / 本算法实现二叉树按层打印struct node BiTree vecMaxSize; /存放树结点int layerMaxSize; /结点所在的层int locateMaxSize; /打印结点的位置int front,rear; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 10 页q; /定义队列q int i,j=1,k=0,nLocate; q.front=q.rear=0; /初始化队列q 队头、队尾coutn ; q.vec

17、q.rear=T; /二叉树的根结点入队q.layerq.rear=1; q.locateq.rear=20; q.rear=q.rear+1; while(q.frontq.rear) T=q.vecq.front; 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) /存

18、在左子树，将左子树的根结点入队列 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(char ch) coutdata);

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

20、der(T-lchild); /后序遍历左子树Postorder(T-rchild); /后序遍历右子树Visit(T-data); /访问根结点 /7.输出叶子结点void PreorderLeaf(BiTree T) / 先序遍历二叉树并输出叶子结点，T 为指向二叉树根结点的指针if(T!=NULL) if(T-lchild=NULL&T-rchild=NULL) Visit(T-data); /访问根结点PreorderLeaf(T-lchild); /先序遍历左子树PreorderLeaf(T-rchild); /先序遍历右子树 /8.输出叶子结点的个数int LeafCount(Bi

21、Tree T) int LeafNum; 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; /9.输出二叉树的深度精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 10 页int PostorderDepth(BiTree T) / 后序遍历求二叉树深度的递归算法int hl,hr,max; if(T!=NU

22、LL) hl=PostorderDepth(T-lchild); /求左子树的深度hr=PostorderDepth(T-rchild); /求右子树的深度max=hlhr?hl:hr; /得到左右子树深度较大者return (max+1); /返回树的深度 else return 0; /空树返回 0 /10. 以括号形式输出二叉树void output(BiTree T) if(T!=NULL) coutdata; if(T-lchild!=NULL|T-rchild!=NULL) coutlchild); if(T-rchild!=NULL) coutrchild); cout); /1

23、1.主工作函数，操作区用户界面void mainwork() int yourchoice; coutn-欢迎使用二叉树基本操作程序-n; coutn 菜单选择nn; cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4. 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; while(!(yourchoice=1|yourchoice=2|yourchoice=4|yourchoice=5| yo

24、urchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) coutyourchoice; while(1) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 10 页 switch(yourchoice) case 1:cout 树的形状为：; TranslevelPrint(T);break; case 2:cout先序遍历为： ; Preorder(T);break; case 3:cout中序遍历为： ; Inorder(T);break; case 4:cout后序遍历为： ; Post

25、order(T);break; 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

26、菜单选择nn; cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4. 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; /endwhile(1) /endmainwork /12.主函数void main() cout 首先请输入二叉树结点序列：n; CreateBiTree(T); cout 请按菜单提示操作：n; mainwork(); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 10 页