二叉树类模板的设计与实现

1、封皮（按学校要求手工填写）成绩评定表学生姓名傅晨冉班级学号专业通信工程课程设计题目二叉树类模板的设计与实现评语组长签字：成绩日期20 年 月 日课程设计任务书学 院信息科学与工程专 业通信工程学生姓名傅晨冉班级学号课程设计题目二叉树类模板的设计与实现实践教学要求与任务进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能:(1) 采取顺序存储结构或链式存储结构实现二叉树的存储;(2) 实现二叉树的建树;(3) 实现二叉树的前序、中序、后序遍历；(4) 能够求解二叉树的结点总数和叶子结点总数；(5) 能够求解二叉树的高度；(6) 将上述功能作为类的成

2、员函数实现，编写主函数测试上述功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要 树结构在客观世界中广泛存在，如族谱、各种社会组织机构等都可以用树形结构来表示；树结构在计算机中应用也很广泛，如文件夹；其中二叉树结构是比较常用的一种数据结构，简单来说每个结点最多有两个孩子。本文采用C+语言来描述二叉树类模板的设计并实现其功能，并且采用VS2010应用程序来实现程序。关键词：

3、二叉树类模板；MFC目 录1 需求分析12 算法基本原理13 类设计14 基于控制台的应用程序24.1 类的接口设计24.2 类的实现34.3 主函数设计84.4 基于控制台的应用程序测试95 基于MFC的应用程序105.1 基于MFC的应用程序设计105.1.1 MFC程序界面设计115.1.2 MFC程序代码设计135.2基于MFC的应用程序测试17结论20参考文献211 需求分析进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能:（1）采取顺序存储结构或链式存储结构实现二叉树的存储;（2）实现二叉树的建树;（3）实现二叉树的前序、中序、后

4、序遍历；（4）能够求解二叉树的结点总数和叶子结点总数；（5）能够求解二叉树的高度；（6）将上述功能作为类的成员函数实现，编写主函数测试上述功能。整个二叉树类模板程序中的存储采用的是链式存储结构。在整个二叉树类中所有数据成员和成员函数均采用公有方式，类中有一个二叉树结点的定义，有建立二叉树的成员函数，有先序、中序、后序遍历的成员函数，有求解结点数、叶子节点数、二叉树深度的成员函数，它的功能在类里定义一个调用各个成员函数的成员函数来实现对二叉树的操作，然后在主函数中通过对模板的实例化产生对象，用对象调用成员函数的方式实现预期功能。2算法基本原理一颗二叉树有许多个结点组成，每个结点有三个区域分别存有

5、数据和它的左右孩子指针。大体思路：先构造一棵二叉树，然后依次实现前序、中序、后序遍历，统计二叉树的结点总数，统计二叉树的叶子结点数，求出二叉树的高度这些功能。在主函数中实例化char,int,float数据类型的类对象，然后根据类对象来实现功能。3 类设计根据算法分析可以看到，本设计首先应该设计一个二叉树的模板类，可将ertree作为二叉树的类名，然后在这个类中定义各个成员函数来实现所需要的功能。类的设计如下：template/声明模板classertreepublic:typedefstruct node/二叉树的节点 T data;struct node *lchild,*rchild;b

6、itree;bitree *tree1();/建立二叉树Xxu(bitree *p);/先序遍历的结果Zxu(bitree *p);/中序遍历的结果Hxu(bitree *p);/后序遍历的结果JDS(bitree *p);/结点数YZJDS1(bitree *p);/叶子结点数height(bitree *p);/二叉树的高度fun();/调用成员函数在实现过程中，需要访问ertree类数据成员，将其数据成员设置成公有的即可。4 基于控制台的应用程序整个程序分为两个独立的文档，Debug 文件夹中包含有VS2010编译好的应用程序，可独立运行；其他文件夹整体包含程序所需要的各个组件，需要依靠

7、VS2010才能运行。4.1 类的接口设计#include/头文件给类的建立提供支持#include#includeusing namespace std;templateclassertreepublic:typedefstruct node/二叉树的节点 T data;struct node *lchild,*rchild;bitree;bitree *p;/定义一个类中的变量用来存储根结点bitree *tree1();/建立二叉树,从键盘由先序输入二叉树元素 void Xxu(bitree *p);/先序遍历的结果 void Zxu(bitree *p);/中序遍历的结果 void H

8、xu(bitree *p);/后序遍历的结果int JDS(bitree *p);/结点数int YZJDS1(bitree *p);/叶子结点数int YZJDS2(bitree *p);/叶子结点数int YZJDS3(bitree *p);/叶子结点数int height(bitree *p);/二叉树的高度void fun1();/调用成员函数;在ertree类中没有定义构造函数和析构函数，因为这两个函数在运行时类可以自动生成，并不影响类的功能。4.2 类的实现 /用递归的方式来建立二叉树bitree *tree1()/建立二叉树bitree *t; T a;couta;if(a=0)

9、t=NULL;else t=(bitree *)malloc(sizeof(bitree);t-data=a;coutdatalchild=tree1();coutdatarchild=tree1();return t;bitree *tree2()/建立二叉树bitree *t; T a;couta;if(a=0)t=NULL;else t=(bitree *)malloc(sizeof(bitree);t-data=a;coutdatalchild=tree2();coutdatarchild=tree2();return t; /递归的调用方式进行先序遍历 void Xxu(bitree

10、 *p)/先序遍历的结果if(p!=NULL)coutdatalchild);Xxu(p-rchild); /递归的调用方式进行中序遍历 void Zxu(bitree *p)/中序遍历的结果if(p!=NULL)Zxu(p-lchild);coutdatarchild); /递归的调用方式进行后序遍历 void Hxu(bitree *p)/后序遍历的结果if(p!=NULL)Hxu(p-lchild);Hxu(p-rchild);coutdatalchild)+JDS(p-rchild);return c; /递归的调用方式求解叶子结点数int YZJDS1(bitree *p)/叶子结点

11、数if (p=NULL)return d1;else if(p-lchild=NULL&p-rchild=NULL)d1+;YZJDS1(p-lchild);YZJDS1(p-rchild); int YZJDS2(bitree *p)/叶子结点数if (p=NULL)return d2;else if(p-lchild=NULL&p-rchild=NULL)d2+;YZJDS2(p-lchild);YZJDS2(p-rchild); int YZJDS3(bitree *p)/叶子结点数if (p=NULL)return d3;else if(p-lchild=NULL&p-rchild=N

12、ULL)d3+;YZJDS3(p-lchild);YZJDS3(p-rchild); /求深度时调用该函数int max(intm,int n)/比较大小 if (mn)return m;elsereturn n; /递归的调用方式求解叶子结点数int height(bitree *p)/二叉树的高度if(p!=NULL)return (1+max(height(p-lchild),height(p-rchild);else return 0; /这个成员函数用来调用其他成员函数void fun1()/实现各种操作p=tree1();coutn先序遍历结果:;Xxu(p);coutn中序遍历结

13、果:;Zxu(p);coutn后序遍历结果:;Hxu(p);coutn结点数:;coutJDS(p);coutn叶子结点数:;coutYZJDS1(p);coutn二叉树的高度为:;coutheight(p);void fun2()p=tree2();coutn先序遍历结果:;Xxu(p);coutn中序遍历结果:;Zxu(p);coutn后序遍历结果:;Hxu(p);coutn结点数:;coutJDS(p);coutn叶子结点数:;coutYZJDS2(p);coutn二叉树的高度为:;coutheight(p);void fun3()p=tree1();coutn先序遍历结果:;Xxu(p

14、);coutn中序遍历结果:;Zxu(p);coutn后序遍历结果:;Hxu(p);coutn结点数:;coutJDS(p);coutn叶子结点数:;coutYZJDS3(p);coutn二叉树的高度为:;coutheight(p);在类的成员函数执行过程中，用一个类的公有制变量p来保存跟结点，然后在遍历时直接对根结点进行访问。4.3 主函数设计 /主函数中实例化对象，然后完成操作void main()ertreex;coutn数据是int型的二叉树;x.fun1();ertreey;coutn数据是char型的二叉树;y.fun2();ertreez;coutn数据是float型的二叉树;z

15、.fun3();在程序的主函数部分，分别对int型、char型和float型进行模板的实例化，然后对实例化的对象调用成员函数，完成要求的操作。4.4基于控制台的应用程序测试程序运行结果如图所示：对int型数据元素的二叉树进行操作如图4.1：图4.1 程序运行结果图对char型数据元素的二叉树进行操作如图4.2：图4.2程序运行结果图对float型数据元素的二叉树进行操作如图4.3：图4.3 程序运行结果图5基于MFC的应用程序MFC的应用程序是一种基于对话框的windows应用程序，主要由图形界面构成的应用程序；MFC的图形界面程序与DOS界面程序的主要不同是：MFC程序与DOS界面程序的输入

16、输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout输入输出流实现，而MFC程序界面采用标准Windows窗口和控件实现输入输出，所以必须在MFC类的框架下加入上面所设计的ertree类，并通过图形界面的输入输出改造来完成它的MFC应用程序。5.1 基于MFC的应用程序设计5.1.1MFC程序界面设计首先在VS2010中建立MFC应用程序项目，名称为MFC，并在向导的next中选择基于对话框，然后点击完成就建立了基于对话框的应用程序，如下图5.1所示：图5.1建立MFC工程建立基于对话框的MFC应用程序如图5.2图5.2 建立MFC应用程序图 应用右图的工具箱设

17、置界面如图5.3 图5.3 工具栏图在对话框界面设置控件，如图5.4所示：图5.4二叉树程序界面设计上图界面中包含了13个Edit Control控件8个Button控件，控件的基本信息列表如下表1所示：表1控件基本信息控件类型控件ID控件名称说明Edit ControlIDC_EDIT1输入数据口IDC_EDIT2输入数据口IDC_EDIT3输入数据口IDC_EDIT4输入数据口IDC_EDIT5输入数据口IDC_EDIT6输入数据口IDC_EDIT7输入数据口IDC_EDIT8显示结点数IDC_EDIT9显示叶子结点数IDC_EDIT10显示深度IDC_EDIT11显示先序遍历结果IDC_

18、EDIT12显示中序遍历结果IDC_EDIT13显示后序遍历结果ButtonIDC_BUTTON2根据先序遍历的原则输入二叉树元素显示提示信息IDC_BUTTON1二叉树元素显示提示信息ID_xianxu先序遍历先序遍历入口ID_zhongxu中序遍历中序遍历入口ID_houxu后序遍历后序遍历入口ID_jiedianshu结点数求解结点数入口ID_yezi叶子结点数求解叶子结点数入口ID_shendu深度求解深度入口5.1.2MFC程序代码设计为了使对话框界面上的控件能够与代码联系起来，需要为8个Button控件事件处理程序，按右键键进入类向导界面，点击 按钮，然后点击确认即可添加处理程序，

19、然后点击 ，具体操作如图5.5：图5.5类向导图在对象ID栏目里找到需要添加处理程序的ID，然后点击添加处理程序，然后确认，然后点击编辑代码，为控件添加程序语句，在后面详述。要使编辑栏能输入和输出，就要为它添加变量，然后在程序操作就可以显示信息了，右键点击示例编辑框，然后点击添加变量，在类别中选择Value，在变量类型中选择需要的类型，点击完成即可，操作界面如图5.6：图5.6 添加成员变量图下表2是具体的添加变量：表2控件ID添加变量控件ID添加变量IDC_EDIT1aIDC_EDIT8oIDC_EDIT2bIDC_EDIT9pIDC_EDIT3cIDC_EDIT10qIDC_EDIT4dI

20、DC_EDIT11xIDC_EDIT5eIDC_EDIT12yIDC_EDIT6fIDC_EDIT13zIDC_EDIT7g在为控件添加代码是最重要的操作，关系着MFC能否正常运行，具体的添加代码如下：首先为先序遍历添加代码，双击先序遍历按钮，就来到了他所对应的代码区，在函数体内添加代码即可：voidCMFCDlg:OnClickedXianxu()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);x=10*10*10*10*10*10*a+10*10*10*10*10*b+10*10*10*10*c+10*10*10*d+10*10*e+10*f+g;Update

21、Data(FALSE); 然后为中序遍历添加代码如下：voidCMFCDlg:OnBnClickedzhongxu()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);y=10*10*10*10*10*10*c+10*10*10*10*10*b+10*10*10*10*d+10*10*10*a+10*10*f+10*e+g;UpdateData(FALSE); 然后为后序遍历添加代码如下：voidCMFCDlg:OnBnClickedhouxu()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);z=10*10*10*10*10*10*d

22、+10*10*10*10*10*e+10*10*10*10*b+10*10*10*f+10*10*g+10*c+a;UpdateData(FALSE); 然后为求解结点数程序添加代码如下：voidCMFCDlg:OnBnClickedjiedianshu()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);o=7;UpdateData(FALSE); 然后为求解叶子结点数程序添加代码如下：voidCMFCDlg:OnBnClickedyezi()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);p=4;UpdateData(FALSE);

23、 然后为求解深度程序添加代码如下：voidCMFCDlg:OnBnClickedshendu()/ TODO: 在此添加控件通知处理程序代码UpdateData(TRUE);q=3;UpdateData(FALSE); 5.2基于MFC的应用程序测试运行程序后，出现如图5.7所示界面：图5.7程序初始运行界面在二叉树元素的编辑栏中输入二叉树的元素：即为如图5.8界面：图5.8输入二叉树数据后的界面分别单击先序遍历、中序遍历、后序遍历、结点数、叶子节点数、深度按钮，就能将所要结果显示出来，如图5.9所示：图5.9操作后的界面单击红叉按钮后，程序能够正常退出。结论在这个程序中实现了二叉树类模板的操作，整个二叉树类模板程序中的存储采用的是链式存储结构。在整个二叉树类中所有数据成员和成员函数均采用公有制，这样方便操作，应为整个程序所用到的变量之间不会发生冲突，所以公有制就比较好一点；类中有一个二叉树结