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

封皮（按学校要求手工填写）成绩评定表学生姓名傅晨冉班级学号1203060408专业通信工程课程设计题目二叉树类模板的设计与实现评语组长签字：成绩日期20年月日课程设计任务书学院信息科学与工程专业通信工程学生姓名傅晨冉班级学号1203060408课程设计题目二叉树类模板的设计与实现实践教学要求与任务进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能:(1)采取顺序存储结构或链式存储结构实现二叉树的存储;(2)实现二叉树的建树;(3)实现二叉树的前序、中序、后序遍历；(4)能够求解二叉树的结点总数和叶子结点总数；(5)能够求解二叉树的高度；(6)将上述功能作为类的成员函数实现，编写主函数测试上述功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要树结构在客观世界中广泛存在，如族谱、各种社会组织机构等都可以用树形结构来表示；树结构在计算机中应用也很广泛，如文件夹；其中二叉树结构是比较常用的一种数据结构，简单来说每个结点最多有两个孩子。本文采用C++语言来描述二叉树类模板的设计并实现其功能，并且采用VS2010应用程序来实现程序。关键词：二叉树类模板；MFC目录1需求分析..............................................................12算法基本原理..........................................................13类设计................................................................14基于控制台的应用程序..................................................24.1类的接口设计.......................................................24.2类的实现...........................................................34.3主函数设计.........................................................84.4基于控制台的应用程序测试...........................................95基于MFC的应用程序...................................................105.1基于MFC的应用程序设计............................................105.1.1MFC程序界面设计...........................................115.1.2MFC程序代码设计...........................................135.2基于MFC的应用程序测试.............................................17结论....................................................................20参考文献................................................................2111需求分析进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能:（1）采取顺序存储结构或链式存储结构实现二叉树的存储;（2）实现二叉树的建树;（3）实现二叉树的前序、中序、后序遍历；（4）能够求解二叉树的结点总数和叶子结点总数；（5）能够求解二叉树的高度；（6）将上述功能作为类的成员函数实现，编写主函数测试上述功能。整个二叉树类模板程序中的存储采用的是链式存储结构。在整个二叉树类中所有数据成员和成员函数均采用公有方式，类中有一个二叉树结点的定义，有建立二叉树的成员函数，有先序、中序、后序遍历的成员函数，有求解结点数、叶子节点数、二叉树深度的成员函数，它的功能在类里定义一个调用各个成员函数的成员函数来实现对二叉树的操作，然后在主函数中通过对模板的实例化产生对象，用对象调用成员函数的方式实现预期功能。2算法基本原理一颗二叉树有许多个结点组成，每个结点有三个区域分别存有数据和它的左右孩子指针。大体思路：先构造一棵二叉树，然后依次实现前序、中序、后序遍历，统计二叉树的结点总数，统计二叉树的叶子结点数，求出二叉树的高度这些功能。在主函数中实例化char,int,float数据类型的类对象，然后根据类对象来实现功能。3类设计2根据算法分析可以看到，本设计首先应该设计一个二叉树的模板类，可将ertree作为二叉树的类名，然后在这个类中定义各个成员函数来实现所需要的功能。类的设计如下：templateclassT//声明模板classertree{public:typedefstructnode{//二叉树的节点Tdata;structnode*lchild,*rchild;}bitree;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编译好的应用程序，可独立运行；其他文件夹整体包含程序所需要的各个组件，需要依靠VS2010才能运行。4.1类的接口设计3#includestdlib.h//头文件给类的建立提供支持#includemalloc.h#includeiostreamusingnamespacestd;templateclassTclassertree{public:typedefstructnode{//二叉树的节点Tdata;structnode*lchild,*rchild;}bitree;bitree*p;//定义一个类中的变量用来存储根结点bitree*tree1();//建立二叉树,从键盘由先序输入二叉树元素voidXxu(bitree*p);//先序遍历的结果voidZxu(bitree*p);//中序遍历的结果voidHxu(bitree*p);//后序遍历的结果intJDS(bitree*p);//结点数intYZJDS1(bitree*p);//叶子结点数intYZJDS2(bitree*p);//叶子结点数intYZJDS3(bitree*p);//叶子结点数intheight(bitree*p);//二叉树的高度voidfun1();//调用成员函数};在ertree类中没有定义构造函数和析构函数，因为这两个函数在运行时类可以自动生成，并不影响类的功能。4.2类的实现//用递归的方式来建立二叉树bitree*tree1(){//建立二叉树bitree*t;4Ta;cout输入元素;cina;if(a==0)t=NULL;else{t=(bitree*)malloc(sizeof(bitree));t-data=a;coutt-data的左子树;t-lchild=tree1();coutt-data的右子树;t-rchild=tree1();}returnt;}bitree*tree2(){//建立二叉树bitree*t;Ta;cout输入元素;cina;if(a=='0')t=NULL;else{t=(bitree*)malloc(sizeof(bitree));t-data=a;coutt-data的左子树;t-lchild=tree2();coutt-data的右子树;t-rchild=tree2();}returnt;}//递归的调用方式进行先序遍历voidXxu(bitree*p){//先序遍历的结果if(p!=NULL){coutp-data'';Xxu(p-lchild);5Xxu(p-rchild);}}//递归的调用方式进行中序遍历voidZxu(bitree*p){//中序遍历的结果if(p!=NULL){Zxu(p-lchild);coutp-data'';Zxu(p-rchild);}}//递归的调用方式进行后序遍历voidHxu(bitree*p){//后序遍历的结果if(p!=NULL){Hxu(p-lchild);Hxu(p-rchild);coutp-data'';}}//递归的调用方式求解结点数intJDS(bitree*p){//结点数intc;if(p==NULL)c=0;elsec=1+JDS(p-lchild)+JDS(p-rchild);returnc;}//递归的调用方式求解叶子结点数intYZJDS1(bitree*p){//叶子结点数if(p==NULL)returnd1;else{if(p-lchild==NULL&&p-rchild==NULL)d1++;YZJDS1(p-lchild);YZJDS1(p-rchild);}}intYZJDS2(bitree*p){//叶子结点数6if(p==NULL)returnd2;else{if(p-lchild==NULL&&p-rchild==NULL)d2++;YZJDS2(p-lchild);YZJDS2(p-rchild);}}intYZJDS3(bitree*p){//叶子结点数if(p==NULL)returnd3;else{if(p-lchild==NULL&&p-rchild==NULL)d3++;YZJDS3(p-lchild);YZJDS3(p-rchild);}}//求深度时调用该函数intmax(intm,intn)//比较大小{if(mn)returnm;elsereturnn;}//递归的调用方式求解叶子结点数intheight(bitree*p){//二叉树的高度if(p!=NULL){return(1+max(height(p-lchild),height(p-rchild)));}elsereturn0;}//这个成员函数用来调用其他成员函数voidfun1(){//实现各种操作p=tree1();cout\n先序遍历结果:;7Xxu(p);cout\n中序遍历结果:;Zxu(p);cout\n后序遍历结果:;Hxu(p);cout\n结点数:;coutJDS(p);cout\n叶子结点数:;coutYZJDS1(p);cout\n二叉树的高度为:;coutheight(p);}voidfun2(){p=tree2();cout\n先序遍历结果:;Xxu(p);cout\n中序遍历结果:;Zxu(p);cout\n后序遍历结果:;Hxu(p);cout\n结点数:;coutJDS(p);cout\n叶子结点数:;coutYZJDS2(p);cout\n二叉树的高度为:;coutheight(p);}voidfun3(){p=tree1(