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

摘要针对现实世界中许多关系复杂得数据，如人类社会得家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在得具有分支关系或层次特性得对象如操作系统得文件构成、人工智能与算法分析得模型表示以及数据库系统得信息组织形式等，用线性结构难以把其中得逻辑关系表达出来,必须借助于数与图这样得非线性结构，因此在以模拟客观世界问题,解决客观世界问题为主要任务得计算机领域中树型结构就是信息得一种重要组织形式,树有着广泛应用。在树型结构得应用中又以二叉树最为常用。二叉树就是一种非常重要得非线性结构,所描述得数据有明显得层次关系，其中得每个元素只有一个前驱,二叉树就是最为常用得数据结构，它得实际应用非常广泛，二叉树得遍历方式有三种，前序遍历,中序遍历，后序遍历,先序遍历得顺序为：NLR先根结点，然后左子树，右子树;中序遍历顺序为;LNR先左子树,然后根结点,右子树;后序遍历顺序为：RN先左子树,然后右子树,根结点。由前序与中序遍历，有中序与后序遍历序列可以唯一确定一棵二叉树.对于给几个数据得排序或在已知得几个数据中进行查找，二叉树均能提供一种十分有效得方法,比如在查找问题上,任何借助于比较法查找长度为得一个序表得算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表得有效方法根据树得数学理论,对于算法分析得某些最有启发性得应用，就是与给出用于计算各种类型中不同树得数目得公式有关得.本文对二叉树以及二叉树得各种功能做介绍以及写出一些基本得程序，让我们对二叉树得理解有更好得效果.关键词:二叉树得遍历;左子树;右子树；递归目录1、问题概述1、问题描述31、2需求分析31、3设计内容与要求31、4流程图及结构图2、概要设计32、1数据结构设计：32、2源程序代码3、调试分析、1调试中得问题4、测试结果总结3参考文献1、问题概述、1问题描述创建二叉树并遍历基本要求:该程序集成了如下功能：(1）二叉树得建立（2)递归与非递归先序，中序与后序遍历二叉树(3）按层次遍历二叉树（4）交换二叉树得左右子树(5)输出叶子结点（6）递归与非递归计算叶子结点得数目1、需求分析分先序遍历,中序遍历与后序遍历三种情况考虑。1、先序遍历，当二叉树非空时按以下顺序遍历,否则结束操作： 访问根结点; 按先序遍历规则遍历左子树; 按先序遍历规则遍历右子树;2、 中序遍历，当二叉树非空时按以下顺序遍历,否则结束操作： 按中序遍历规则遍历左子树； 访问根结点； 按中序遍历规3遍历右子树.3、 后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作: 按后序遍历规则遍历左子树； 按后序遍历规则遍历右子树； 访问根结点.1、3设计内容与要求对任意给定得二叉树（顶点数自定）建立它得二叉链表存贮结构,并利用栈得五种基本运算(清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树得先序、中序、后序三种周游，输出三种周游得结果。1、4流程图及结构图YESYESNONO开始i=0inbtreetypenewNodeMultiplexroot=newNodei+结束就是否为空returnroot图、1 流程图 b c d e f a图1、2二叉链表存储结构模拟图、概要设计2、1数据结构设计：1。二叉树结点数据类型定义为:teplateypenamestrcBNdeBiNde*chil，chd;/指向左孩子得指针aa；结点数据信息;2。二叉树数据类型定义为：templtetypeeclassiTretemplattypenamerindostreaoerator(stemo，BiTreTbt);ublic:iTre(）;/无参构造函数Bire(intm);有参空构造函数BiTree(T,intum,Tnone）;/有参构造函数BiTree（）；/析构函数idpreode（)；/递归前序遍历oidnoder(）;/递归中序遍历odpostorder（）;/递归后续遍历voidlevelord（)；/层序遍历intcunt(）;/计算二叉树得结点数voddisay（ostrem&os）；/打印二叉树,有层次voidLevelu（);/计算每一层结点数viPreOrder(）；/非递归前序遍历voidPostOrder()；/非递归后序遍历oidcrat();/创建二叉树prtectd:以下函数供上面函数调用/对应相同功能Vocreat(BiNodeT*root)；/创建odrelase（BNde&rot）;/删除idTBild(ary,intnu,Tno，intid);/用数组创建二叉树voidPreOder（iNoe*ro);/前序遍历idotOrd（BiNdroot）；/层序遍历vdprorder（BiNodeToot)；递归前序遍历voidinore（iNeTroot）；递归中序遍历voidpstorer（BiNdeTroot）;/递归后续遍历voidevelrder(BiNod*ro）；/层序遍历icoun(BNodT*root）；/计算结点数oiddislay（osream&os，BiNoeoot,Tva,Tv，BNodevate：iNodeT*rotpt;；2、源程序代码#inclde ioreamusin namse std；/*/二叉树结点类得定义templaestut BTodeda； TNodeT Lchi,*Rhld; BTNde（T nodVueT（)，BToe leode =NL,BTNoeT*ghtNode=ULL ) ：daa（odValue)，Lchild(letNoe），child（rightod) /可选择参数得默认构造函数;/*/二叉树得建立emlaecass voidcreateBinTree(BTNodeT * &ro ) TNe = roo； BTNode k； T noealue ； cinnodelue; if（nodeVlue=1) oot=ULL； else o=ewTd(）； rtta =ndeVal; reainee(oo-hild); createBiree（oo-ch)； /*/二叉树得先序遍历emplae cls Toid preOrr( TNode* p) if（p） coutdat ； preOdr（-hil）; preOrder（p-Rcld）; /*/二叉树得中序遍历emplat & p） if（p） nOrder（Lchid)； coutptcild)； /*/二叉树得后序遍历teplte lasTvoid levrdr（NdT *& p） i(p） lvelOrdr（pLhil）； lveOrdr(pRcild）; dta” ”; /*/统计二叉树中结点得个数template p） if(p=NUL) rern; rtrn +counNode（pLhild)+cunNde（-Rchil)；/*/求二叉树得深度tempateclas t dph（TNodeT & p） if（ = NULL) rtn 1； it h1 = depth（Lchid）； in h2 deph（chid); i(h12)reur （1+)； rturn h2+；/*/二叉树得消毁操作telaelss TTNeT dstoy(BNeT ) /消毁函数，用来消毁二叉树中得各个结点 if(） rern esroy(p-hild); reurnetroy（-Rchild）； deet p； */主函数得设计 int mn （) TNodeit oote= NULL; nt choiced = 0; whie（tr) system(cls”）; ou”nnn -主界面-n”; cou” 1、创建二叉树 2、先序遍历二叉树; cou 3、中序遍历二叉树 、后序遍历二叉树n； cou 5、统计结点总数 6、查瞧树深度 n; out” 、消毁二叉树 0、退出nn; cout” 请选择操作:； cinchice； f（choicd = ) reun0; else if(coiced = 1） system（cs); cou”请输入每个结点，回车确认，并以1结束:; creatinTree(rotNode)； else if(hoced = 2) system(cs）； cu先序遍历二叉树结果:; preOrder(rootNode）； coutendl； syse(paus”）； se if（choiced= ) sse(ls）； cout中序遍历二叉树结果:”; nOrder（rootNoe); cutendl; sytm（as”)； els f（hoicd = 4） system（cls）； cot后序遍历二叉树结果:n”; lveOrer(ooNod）； couenl； sytem(pae）； else i（choiced =5） system(cs”)； n count=cotNoe(rotNde); u”二叉树中结点总数为counten; ytem（pause); lseif（choic =） syste(”cs）； it dp = ep（rotNode）; cou”此二叉树得深度为”deendl； sysm(paue”)； ese if（choid = 7） sstem（”cls”）; cou”二叉树已被消毁！n； dero（otNde)； coendl; sytem(”pause”); els sysm(”ls”）； cout”nnnnn错误选择!； 3、调试分析3、1调试中得问题创建二叉树：依次输入二叉树前序遍历序列,构建相应得二叉树。二叉树遍历：递归算法、非递归算法测试,调用相应函数进行测试，结果正确。求二叉树深度与结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数:调用levelNum（）函数,测试结果正确。调试时遇到诸多问题，其中最主要得问题就是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题.4、测试结果（1)初始界面：主界面所包含得内容图4、初始界面图(）运行结果：进行操作，输入每个结点，显示结果如下图、创建二叉树进行操作2，执行结果如下：图4、二叉树先序遍历进行操作3,执行结果如下：图4、4二叉树中序遍历进行操作4,执行结果如下：图、5二叉树后序遍历：进行操作5,执行结果如下:图4、统计二叉树节点进行操作6,执行结果如下：图4、查瞧树深度总结要能很好得掌握编程,仅仅通过几个简单得程序得编写时无法达成得,更需要大量积累与深入才可能通过本次课程设计。有关一个课题得所有知识不仅仅就是在课本上,多查阅一些资料能够更好得完成课题,这就需要一种能力,即自学能力。本次课程设计还让我认识到自己得缺点。本次选得课题就是二叉树得遍历，因为本学期所学得就就是二叉树等数据结构,所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决得问题，就像老师请教,并查阅相关资料。经过慢慢得调试，最终测试成功。这次课程设计让我所学到得数据结构知识发挥得淋漓尽致，而且还拓展了我得知识面，使我更加熟练得掌握各种方法。总之,这次课程设计增强了我得自学能力，拓展了我得知识面,让我对数据结构更加了解。参考文献1 严蔚敏 吴伟民 数据结构（语言版)清华大学出版社, 2009年月2 谭浩强C程序设计（第三版)清华大学出版社 009年1月