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

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

1、精选学习资料 - - - - - - - - - 二叉树基本操作演示程序的设计与实现2022 级电器信息类 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、系统功

3、能设计本程序除了完成二叉树的创建功能外仍设置了9 个子功能菜单；由于这9 个子功能都是建立在二叉树的构造上的,所以二叉树的创建由主函数 述如下：main实现； 9 个子功能的设计描树状输出二叉树；树状输出二叉树由函数 TranslevelPrint 实现；当用户挑选此功能时,系统即以树状的形式输出用户所创建的二叉树；先序遍历二叉树；由函数 出先序序列；Preorder实现；该功能依据先序遍历拜访二叉树的方法输中序遍历二叉树；由函数 Inorder 实现；该功能依据中序遍历拜访二叉树的方法输出中序序列；后序遍历二叉树；由函数 Postorder实现； 该功能依据后序遍历拜访二叉树的方法输出后序序

4、列；名师归纳总结 - - - - - - -第 1 页,共 10 页精选学习资料 - - - - - - - - - 输出叶子结点；该功能采纳先序遍历二叉树的方法依次输出叶子结点；由函数Preorderleaf 实现；输出叶子结点个数；该功能运算并输出二叉树中叶子结点的个数,由 LeafCount 实现；采纳递归算法运算二叉树中叶子结点的个数,算法思想是：当二叉树为空树时,叶子结点总数为 0；当二叉树只有 1 个结点时,叶子结点总数为 1；否就,叶子结点个数等于左右子树叶子结点数之和；输出二叉树的深度；该功能输出二叉树的深度,由函数 后序遍历的递归算法求二叉树的深度；PostorderDept

5、h 实现,采纳括号形式输出二叉树；以括号形式输出二叉树由函数,由函数 output 实现；当用户挑选此功能时,系统即以括号形式输出二叉树；退出；由 exit0 函数实现；三、模块设计1、模块设计本程序包含三个模块,主程序模块、建立二叉树模块和工作区挑选模块；其调用关系如图 2 所示；主程序模块建立二叉树模块 工作区挑选模块图 2 模块调用示意图2、系统子程序用功能设计本系统共设置 12 个子程序,各子程序的函数名及功能说明如下：void CreateBiTreeBiTree &T / 先序建立二叉树void TranslevelPrintBiTree T / 树形打印二叉树void Visit

6、char ch / 输出结点void PreorderBiTree T / 先序遍历二叉树void InorderBiTree T / 中序遍历二叉树void PostorderBiTree T / 后序遍历二叉树void PreorderLeafBiTree T / 输出叶子结点int LeafCountBiTree T / 输出叶子结点的个数int PostorderDepthBiTree T / 输出二叉树的深度void outputBiTree 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 第一请输入二叉树结点序列

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

9、中序遍历二叉树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| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9 coutyourchoice; while1 switchyourchoice case 1:cout 树的外形为： ; TranslevelP

10、rintT;break; case 2:cout 先序遍历为： ; PreorderT;break; case 3:cout 中序遍历为： ; InorderT;break; case 4:cout 后序遍历为： ; PostorderT;break; case 5:cout 叶子结点为： ; PreorderLeafT;break; case 6:cout 叶子结点个数为：LeafCountT;break; case 7:cout 二叉树的深度为：PostorderDepthT;break; case 8:cout 括号形式输出二叉树为 :;outputT;break; case 9:sys

11、temcls; exit0; break; default: break; coutn 按任意键连续：; getch; systemcls; coutn-欢迎使用二叉树基本操作程序-n; nn; coutn 菜单挑选cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4. 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; /endwhile1 名师归纳总结 - - - - - - -第 4 页,共

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

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

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

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

16、.树形打印二叉树 void TranslevelPrintBiTree 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.vecq.re

17、ar=T; /二叉树的根结点入队 q.layerq.rear=1; q.locateq.rear=20; q.rear=q.rear+1; whileq.frontq.rear T=q.vecq.front; i=q.layerq.front; nLocate=q.locateq.front; ifji /进层打印时换行 coutnn; j=j+1; k=0; cout ; whilek+nLocate whilek+nLocate-1 cout ; /结点深度掌握横向位置coutdata; q.front=q.front+1; ifT-lchild.=NULL /存在左子树,将左子树的根结点

18、入队列 q.vecq.rear=T-lchild; q.layerq.rear=i+1; q.locateq.rear=intnLocate-pow2,NLAYER-i-1; q.rear=q.rear+1; ifT-rchild.=NULL /存在右子树,将右子树的根结点入队列 q.vecq.rear=T-rchild; q.layerq.rear=i+1; q.locateq.rear=intnLocate+pow2,NLAYER-i-1; q.rear=q.rear+1; /3.输出结点 void Visitchar ch coutdata; /拜访根结点 PreorderT-lchil

19、d; /先序遍历左子树 PreorderT-rchild; /先序遍历右子树 /5.中序遍历二叉树 void InorderBiTree T / 中序遍历二叉树,T 为指向二叉树（或某一子树）根结点的指针 ifT.=NULL InorderT-lchild; /中序遍历左子树 VisitT-data; /拜访根结点 InorderT-rchild; /中序遍历右子树 /6.后序遍历二叉树 void PostorderBiTree T / 后序遍历二叉树,T 为指向二叉树（或某一子树）根结点的指针 ifT.=NULL PostorderT-lchild; /后序遍历左子树 PostorderT-

20、rchild; /后序遍历右子树 VisitT-data; /拜访根结点 /7.输出叶子结点 void PreorderLeafBiTree T / 先序遍历二叉树并输出叶子结点,ifT.=NULL T 为指向二叉树根结点的指针 ifT-lchild=NULL&T-rchild=NULL VisitT-data; /拜访根结点 PreorderLeafT-lchild; /先序遍历左子树 PreorderLeafT-rchild; /先序遍历右子树 /8.输出叶子结点的个数 int LeafCountBiTree T int LeafNum; ifT=NULL LeafNum=0; else

21、ifT-lchild=NULL&T-rchild=NULL LeafNum=1; else LeafNum=LeafCountT-lchild+LeafCountT-rchild; return LeafNum; /9.输出二叉树的深度名师归纳总结 - - - - - - -第 8 页,共 10 页精选学习资料 - - - - - - - - - int PostorderDepthBiTree T / 后序遍历求二叉树深度的递归算法 int hl,hr,max; ifT.=NULL hl=PostorderDepthT-lchild; /求左子树的深度 hr=PostorderDepthT-

22、rchild; /求右子树的深度 max=hlhr.hl:hr; /得到左右子树深度较大者 return max+1; /返回树的深度 else return 0; /空树返回 0 /10. 以括号形式输出二叉树 void outputBiTree T ifT.=NULL coutdata; ifT-lchild.=NULL|T-rchild.=NULL coutlchild; ifT-rchild.=NULL coutrchild; cout; /11.主工作函数,操作区用户界面 void mainwork int yourchoice; coutn-欢迎使用二叉树基本操作程序-n; nn;

23、 coutn 菜单挑选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| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9 coutyourchoice; while1 名师

24、归纳总结 - - - - - - -第 9 页,共 10 页精选学习资料 - - - - - - - - - switchyourchoice case 1:cout 树的外形为： ; TranslevelPrintT;break; case 2:cout 先序遍历为： ; PreorderT;break; case 3:cout 中序遍历为： ; InorderT;break; case 4:cout 后序遍历为： ; PostorderT;break; case 5:cout 叶子结点为： ; PreorderLeafT;break; case 6:cout 叶子结点个数为：LeafCou

25、ntT;break; case 7:cout 二叉树的深度为：PostorderDepthT;break; case 8:cout 括号形式输出二叉树为 :;outputT;break; case 9:systemcls; exit0; break; default: break; coutn 按任意键连续：; getch; systemcls; coutn-欢迎使用二叉树基本操作程序-n; nn; coutn 菜单挑选cout 1. 树状输出二叉树2. 先序遍历二叉树n; cout 3. 中序遍历二叉树4. 后序遍历二叉树n; cout 5. 输出叶子结点6. 输出叶子结点个数n; cout 7. 输出二叉树的深度8. 括号形式输出二叉树n; cout 9. 退出n; coutn-n; coutyourchoice; /endwhile1 /endmainwork /12.主函数 void main cout 第一请输入二叉树结点序列：n; CreateBiTreeT; cout 请按菜单提示操作：n; mainwork; 名师归纳总结 - - - - - - -第 10 页,共 10 页