数据结构课程设计--二叉树的遍历

摘要针对现实世界中许多关系复杂得数据，如人类社会得家谱，各种社会组织机构，博弈交通等复杂事物或过程以及客观世界中广泛存在得具有分支关系或层次特性得对象.如操作系统得文件构成、人工智能与算法分析得模型表示以及数据库系统得信息组织形式等，用线性结构难以把其中得逻辑关系表达出来,必须借助于数与图这样得非线性结构，因此在以模拟客观世界问题,解决客观世界问题为主要任务得计算机领域中树型结构就是信息得一种重要组织形式，树有着广泛应用在树型结构得应用中又以二叉树最为常用二叉树就是一种非常重要得非线性结构,所描述得数据有明显得层次关系，其中得每个元素只有一个前驱,二叉树就是最为常用得数据结构，它得实际应用非常广泛，二叉树得遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历得顺序为NLR先根结点，然后左子树，右子树；中序遍历顺序为;LNR先左子树,然后根结点，右子树;后序遍历顺序为LRN先左子树，然后右子树，根结点由前序与中序遍历，有中序与后序遍历序列可以唯一确定一棵二叉树.对于给几个数据得排序或在已知得几个数据中进行查找，二叉树均能提供一种十分有效得方法，比如在查找问题上，任何借助于比较法查找长度为W得一个序表得算法,都可以表示成一株二叉树反之，任何二叉树都对应一个查找有序表得有效方法根据树得数学理论,对于算法分析得某些最有启发性得应用，就是与给出用于计算各种类型中不同树得数目得公式有关得.本文对二叉树以及二叉树得各种功能做介绍以及写出一些基本得程序，让我们对二叉树得理解有更好得效果.关键词:二叉树得遍历;左子树;右子树；递归temp1atecla s s Ti nt d e pt hBTNodeT*p ifp=NULLr et u r n-1；i nt hl=depthp一〉Lehi1d；in t h2=d叩t hp—〉Rchi1d;i fhl h2re t ur nh1+1；r eturn h2+1；}〃***********************************************************************************//二叉树得消毁操作tem p la t ec1a ssTBTNo de T*d est r oyB TNode〈T〉*p//消毁函数，用来消毁二叉树中得各个结点{ifP{re tu md es t royp-L child;re turn des troyp-Rchild；de1et ep；//********************************************************************************//主函数得设计int ma inB TNodei nt*r ootN ode=NULL;i ntchoiced=0;whi1e tr u esystem cis;c ou t〈V”\n\n\n一主界面———\n\n\n；cou t”

1.创建二叉树

2.先序遍历二叉树\ncou t〈〈”

3.中序遍历二叉树

4、后序遍历二叉树\n”；cou t«

5.统计结点总数

6、查瞧树深度\nn;

0、退c out«

7、消毁二叉树出\n\n；cout〈V”请选择操作”cin〉ch oice d；i fchoic e d==0re turn0;else ifch oiced二二1{system clsn;cou t«请输入每个结点，回车确认，并以一1结束:\n”creat eB inTreero o tNode；}else ifc hoi ced==2systemnc1s；c ou t〈先序遍历二叉树结果:\npreOrderrootNode；coutendl；sys t em npaus e”；e1se if choiced==3s yst em nc Is”；cout〈〈中序遍历二叉树结果:\n；i nOrder rootNo d e;c out endl;sy st e m pause；els ei fc hoice d==4systemn cis”；cout后序遍历二叉树结果:\n；1e ve1Or d err oo tNod e；cou t«en d1；sy s tem npa us en；}else ifchoiced==5system nc1s；i nt count=co un tNo d er o otN o de;cout二叉树中结点总数为H〈〈count〈〈end1;s ystempause；}e Ise if choice d==6system,9c1s n；intdep二d epthr ootNode;cou t〈v”此二叉树得深度为“〈〈de p«endl；sys t e mnpaus e’‘；e1seifchoi ced==7s ystem cis;cout〈〈”二叉树已被消毁！\n；de st royr oo tN o de；co ut endl;sy stempause’；}els e{sys temc Is；cout,5\n\n\n\n\n\t错误选择!\n”；}}}调试分析

3.调试中得问题

3.1创建二叉树依次输入二叉树前序遍历序列,构建相应得二叉树二叉树遍历递归算法、非递归算法测试，调用相应函数进行测试，结果正确求二叉树深度与结点数创建一个二叉树，调用相关函数，测试结果正确计算每层结点数:调用levelNum函数,测试结果正确调试时遇到诸多问题，其中最主要得问题就是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题.

4.测试结果1初始界面主界面所包含得内容c mDocuBentsand58t“118$\人（1:1£$1101\桌面\机房软件\21）118\-

3118711.收屋创建二叉树退先遍度叉中树遍叉一遍历

二、历后统树、结点总兄历二消、出毁二叉树数查深

二、---王界面---请选择操作1图初始界面图

4.12运行结果进行操作1,输入每个结点，显示结果如下357^2460c「C:\Docuients and Settings\Adiinistrator\桌面、机房软件Uebug\,angyu.ex屋就次轮结点解蒯,并以-储柬123-14546-17-1-1图、创建二叉树42进行操作2,执行结果如下贯•C:\Docuients andSettings\Adiinistrator\臬面、机后软件\Debug\rangyu.exe，瘢历二义襁黑123456图二叉树先序遍历

4.3进行操作3,执行结果如下:c「C:\Docuicnts andSettings\Adiinistrator\^^\#lJ^^f\Ddmg\，angyu.exe中序遍历二叉椭果:I1234567BOB...图二叉树中序遍历

4.4进行操作4,执行结果如下:c*C:\Docuent sandSettings\Adinist rator\桌面、机房软件\Debug\,angyu.exe后序遍历二叉融桌7645123请按任意键继续・.・图、二叉树后序遍历45进行操作5,执行结果如下:c C:\Docuents and$6七“118式4（1:111衣七1取0i\桌面\机房软件\61）118\,

3118711.©X6|二叉碾照为Z情按在吉健继续..•■图统计二叉树节点

4.6进行操作6,执行结果如下:图查瞧树深度

4.7总结要能很好得掌握编程，仅仅通过几个简单得程序得编写时无法达成得，更需要大量积累与深入才可能通过本次课程设计有关一个课题得所有知识不仅仅就是在课本上，多查阅一些资料能够更好得完成课题,这就需要一种能力，即自学能力本次课程设计还让我认谡到自己得缺点本次选得课题就是二叉树得遍历,因为本学期所学得就就是二叉树等数据结构,所以认为比较适合刚开始认为会很简单，但到后来就出现一些难以解决得问题，就像老师请教，并查阅相关资料经过慢慢得调试，最终测试成功这次课程设计让我所学到得数据结构知识发挥得淋漓尽致，而且还拓展了我得知识面，使我更加熟练得掌握各种方法总之,这次课程设计增强了我得自学能力，拓展了我得知识面,让我对数据结构更加了解参考文献

[1]严蔚敏吴伟民《数据结构（C语言版）》清华大学出版社，2009年9月

[2]谭浩强《C程序设计（第三版）》清华大学出版社2009年1月目录

1.问题概述3问题描述

1.33流程图及结构图

1.

2.

23.调试分析

1、问题描述11创建二叉树并遍历基本要求该程序集成了如下功能1二叉树得建立2递归与非递归先序，中序与后序遍历二叉树3按层次遍历二叉树4交换二叉树得左右子树5输出叶子结点6递归与非递归计算叶子结点得数目需求分析

1.2分先序遍历，中序遍历与后序遍历三种情况考虑

①

1.先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作:

②访问根结点；

③按先序遍历规则遍历左子树；

④按先序遍历规则遍历右子树；

①

2.中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作

②按中序遍历规则遍历左子树；

③访问根结点；

④按中序遍历规3遍历右子树.

①

3.后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作:

②按后序遍历规则遍历左子树；

③按后序遍历规则遍历右子树；

④访问根结点.设计内容与要求

1.3对任意给定得二叉树（顶点数自定）建立它得二叉链表存贮结构，并利用栈得五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树得先序、中序、后序三种周游，输出三种周游得结果流程图及结构图

1.4returnroot结束图、流程图11a图二叉链表存储结构模拟图

1.

2、概要设计2数据结构设计

2.1lo二叉树结点数据类型定义为template〈t ypename T〉str uc t B iNo de BiN o de〈T〉*r child,*1ch i1d;〃指向左孩子得指针T data；II结点数据信息};2o二叉树数据类型定义为tempi ate typen a me Tclass B iTre e{templat etypename Tf rie ndostreamo peratoro str ea mo sbt;p ublic:,BiTre eTB iTr e e;//无参构造函数Bi Tree intm{};//有参空构造函数BiTreeT ary[],int num,T none;//有参构造函数BiTree；〃析构函数v oid preor de r；〃递归前序遍历v oidi nor der;〃递归中序遍历void postorder;〃递归后续遍历void levelord e r；〃层序遍历int c o unt;//计算二叉树得结点数vo id dis p1ay ostreamos；//打印二叉树，有层次void LevelNum;〃计算每一层结点数void PreOrder；〃非递归前序遍历void PostOrder；〃非递归后序遍历v oidcr eat;//创建二叉树pr o tect ed://以下函数供上面函数调用〃对应相同功能Vo id creatBiNodeT*root；〃创建void rele aseB iNo de〈T〉*r oot;//册U除BiN ode〈T〉*B uild Tary[],int num,T non e,int idx；〃用数组创建二叉树void PreOr derB iNo d e〈T*root;〃前序遍历v oid Po stOrd e r BiN od eT*root;//后续遍历vo id Lev eINum B iNodeT*root；//层序遍历void pre order BiNode〈T*r oot；//递归前序遍历void inorderBiNode〈T*root；//递归中序遍历void po storderBiNode〈T〉*root;〃递归后续遍历void1evel orderBiNodeT*ro o t；〃层序遍历int coun tBi Node〈T*root；〃计算结点数v oiddis play ost reamos,BiNo deT*roo t,int dep；//打印s tati cboo1leastma nAnc estor BiNodeT*root,T va,T vb,B iNodeTpr ivate:B iNodeT*roo tpt r;源程序代码

2.2#incl ude iostreamusin gnam espa ce std；〃*************************************************************************************//二叉树结点类得定义templa tec1a ss Tstruc tBT NodeT dat a；B TNodeT*Lehi1d,*R ch i Id;BTNodeCTnode Va1ue=T,BTNo deT*left Node=N ULL,BTNodeT*r ightNode=NULL dat an ode Value,Lchildle ftNo de,Rchild rightNode{〃可选择参数得默认构造函数};//**************************************************************************************〃二叉树得建立templatec1ass Tvoid createBinTreeBTNodeT*root{B TNodeT*p=roo t；BTNodeT*k；T nodeV alue；cin nodeV a lue;if nodeValue——1r oot=NULL；elser oot=new BTNodeT；root—d ata=n ode Vaiu e;c reateBinT ree r oo t-L child;createBi nTreeroot-Rch i1d；〃************************************************************************************〃二叉树得先序遍历t emplatecl assTv oidpreOr de rB TNodeT*p{if pcout p-dat an；preO rderp-L chil d;preOrder p-〉Rc hiId;}//**************************************************************************************〃二叉树得中序遍历t emplate class Tvoid inOr derB TNodeT*pif pinOrderp-Lchi1d；coutp-d ata；inO rder p—Rc hild；}//**************************************************************************************〃二叉树得后序遍历tempi atec lassTvoidlev e1Order BTNodeT*pifP1e velOrd erp-L chil d；1e ve1Orderp—Rc hild;c outp—d ata〈””；}}〃火************************************************************************************〃统计二叉树中结点得个数templateclass T〉int co untNodeBTNode〈T*p{ifp==NUL Lre tu rn0;return1+coun tNode p—L child+countNodep-Rchil d；}//***********************************************************************************〃求二叉树得深度。