二叉树遍历

二叉树遍历姓名：左伟民学号：12714046班级：12医药软件1班一、选题的背景和意义?现实世界中很多问题都可归纳称为树的模型，在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。其中以树和二叉树最为常用，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象，因此在计算机领域里有着广泛应用，如操作系统中的文件管理、编译程序中的语法结构和数据库系统信息组织形式等。?而二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树对学习程序设计、利用计算机解决实际问题特别重要；二叉树的各种复杂运算大都是建立在其三种遍历之上，因此掌握好二叉树的遍历算法是很有必要的。在对二叉树的各种操作中，最基本的操作之一是遍历二叉树。遍历一棵二叉树，就是按照某种规则去访问二叉树的每个结点，而且每个结点仅被访问一次。二、研究目标与主要内容（含论文提纲）研究目标：通过学习二叉树遍历方面的知识以及递归与非递归遍历的利弊，利用VisualC++平台实现递归与非递归二叉树遍历，从而推导出二叉树混合遍历算法，即达到分析二叉树三种遍历递归算法与非递归算法及混合遍历算法的利弊关系。论文大纲：1概述1.1二叉树遍历的背景与意义1.2树2二叉树2.1二叉树的定义2.2二叉树的存储结构2.3二叉树的构建算法3二叉树的遍历3.1开发平台解析3.2二叉树的先序遍历递归算法3.3二叉树的中序遍历递归算法3.4二叉树的后序遍历递归算法4二叉树的非递归算法4.1二叉树的先序遍历非递归算法4.2二叉树的中序遍历非递归算法4.3二叉树的后序遍历非递归算法4.4混合遍历的非递归算法5小结三、拟采取的研究方法、研究手段及技术路线、实验方案等、研究方法：1.文献研究法主要指搜集、鉴别、整理关于二叉树递归遍历与非递归遍历的文献，并通过对文献的研究，形成对二叉树遍历的认识与研究。2.调查法为了达到设想的目的，制定某一计划全面或比较全面地收集研究对象的某一方面情况的各种材料，并作出分析、综合，得到某一结论的研究方法，就是调查法。它的目的可以是全面把握当前二叉树遍历的状况，也可以是为了揭示二叉树遍历存在的问题，弄清前因后果，为进一步的研究或决策提供观点和论据。根据这两种方法，将形成对二叉树遍历的认识和了解。为了编程实现算法，比较全面的对二叉树递归与非递归遍历及混合遍历，并作出分析、综合，总结，从而实现了二叉树遍历递归与非递归及混合遍历算法。研究手段：1.查阅关于二叉树遍历的相关资料，阅读有关二叉树遍历的一些论文、书籍、报刊等，从而了解该题目的研究意义和目的。2.通过上网查资料，认真比较，确定使用VC++6.0为开发平台，实现二叉树遍历递归与非递归求解。3.根据相关的算法要求，画出算法流程图。4.通过进一步的了解，对每个算法流程进行细化，编写相应代码。5.对设计好的程序进行调试，通过调试发现存在的问题并解决，从而达到完成算法的目的。6.最后，整理各阶段的设计记录文档，写成论文稿。实验方案：通过对二叉树遍历递归与非递归算法的学习，依据已经确定的开发平台VisualC++6.0实现基于二叉树遍历求解的递归与非递归算法以及混合遍历算法。并通过数据模拟测试该程序的正确性。四、中外文参考文献目录（理工科专业应在10篇以上，文科类专业应在15篇以上，其中外文文献至少2篇。）[1].CliffordA.Shaffer.APpracticalIntrodutiontoDataStructuresandAlgorithmAnalysis[M]，SecondEdition.PublishingHouseofElectronicIndustry，2002，141-149.[2].[3].严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社,2007，118-132.[4].沈朝辉，赵宏，王刚.数据结构与数据库应用基础教程[M].南开大学出版社，2007，48-59.[5].李根强，谢月娥，吴蓉晖，杜思春.数据结构[M].中国水利水电出版社，2005，99-118.[6].夏克俭，王绍斌.数据结构[M].国防工业出版社，2005，127-152.[7].李彦.遍历二叉树的递归与非递归算法浅析[J].电脑知识与技术，2011，5941-5942.[8].欧阳俊林.遍历二叉树的非递归实现[J].自贡师范高等专科学校学报，2003，126-129.[9].陈朋.后序遍历二叉树的递归和非递归的算法[J].安庆师范学院学报，2005，106-128.[10].马相芬.中序遍历二叉树的算法实现[J].职校论坛，2008，227-281.[11].程冠琦.非递归后序遍历二叉树算法的探讨与分析[J].计算机与网络，207-210.[12].谷立东.用C语言实现二叉树的遍历及其应用[J].牡丹江教育学院学报，2006，142-143.[13].罗帅.二叉树遍历的非递归算法分析与实现[J].软件设计开发，2008，678-680.[14].尹帮治..二叉树遍历的通用递归算法研究与实现[J].人工智能及识别技术，2008，132-134.五、研究的整体方案与工作进度安排（内容、步骤、时间）首先查阅相关资料，阅读关于二叉树遍历的论文和书籍，了解二叉树与二叉树的三种遍历。总结并发现目前的二叉树遍历还存在的不足。通过自己学过的数据结构中的二叉树知识实现二叉树遍历递归算法与非递归算法，并将两种算法进行比较，分析两种算法的优缺点，推导出较为简便的混合遍历算法，最后进行总结。六、研究的主要特点及创新点主要特点：编程二叉树三种遍历的递归与非递归算法，从而实现一次遍历可以得到三种遍历序列的二叉树的混合遍历求解。创新点：本文依据关于二叉树遍历的论文，期刊等，通过利用数据结构中的二叉树知识实现二叉树的三种遍历的递归与非递归算法，通过对于这些算法的比较分析，采用经过一次遍历就可以得到二叉树的先序，中序，和后序三种遍历序列的算法，即二叉树的混合遍历求解。七丶设计(1)整体流程设计技照需求分析设计功能,有创建,遍历,9美素化,插入节点,册l除节点,,査技任意节点,査1言叶子节点,计算树高,退出,一共1ot功能。1ot功能,每t功能为一t模;l央,分别进行设计。真中,遍历和9続化还分别包括三t子选项,而且,9美素化是建立在遍历的基础上的,要先进行遍历,才能确定9美素化的顺序,9美序遍历对应9美序9美素化,中序遍历对应中序9美素化,后序遍历对应后序9続化。该软件的功能中大部分i步及到了通lu3这种方法,利用通lu3,将问题商単化。(3)操作设计才用的是键盘输入的方式,接收用户的键盘输入。只接收単t字符。在遍历和9美素化时,遍历或者9美素化开始后,需要用户技任意键才会继续执行,不能白动执行完。每次软件的执行都是在接收用户输入之后再技任意键继续用户创建=又树的方式:用户在输入时不必输入完全=又树的9美序遍历字符串,只要将完全=又树的每一层的节点输入到文本文档中。在输入时,每输完一层节点,回车,在下一行继续输入节点。节点不存在时用“.”表示。4、同题及解决方案总结(1)节点不能插入。问题描述:当插入节点时,有的节点能插入,有点则不能插入。解決办法:要想插入节点,必须先技到要插入的节点的位置。在裁一开始写的时候,裁在査技位置时犯了一t错误,裁只技査技了根节点,如果根节点不符合条件的话,就不在继续査技。这样就使得节点只能在根节点出插入,从而出现了错误。改进以后,只要能技到位置,并且树高不起过6就能插入。改进后的程序:(2)节点,l、配m除。l口J趣拍述:当翻人要出l除的i点时,1高i出l除,开且出现死机情况。解決办法:在裁认真考慮了子树的册l除过程以后,发现,在裁一开始想的时候,册l除子树,就只是査技子树的言节点,然后后序释放子树的节点。这样的话,问题就出现了,当把子树的言节点释放以后,该节点的又节点的子节点就会为空,从而送接到不确定的位置,出现了不确定的情况,出现死机情况。在明白了这一点以后,裁不再査技子树的言节点,而是査技子树的又节点。这样就選免了又节点的子节点出现不确定情况,从而解決了节点不能册l除的问题。解決问题的程序:的每一层的节点输入到文本文档中。在输入时,每输完一层节点,回车,,在下一行继续输入节点。节点不存在时用“.”表示。(4)树的高度不能白造应屏幕。解決办法:裁一开始在写的时候把节点坐标固定在了创建的时候,所以树的高度是不能白造应屏幕的。现在在创建=又树的时候没有固化节点坐标,只创建树,然后计算树的高度,利用树的高度,,计算节点坐标,然后在画树之前都计算节点坐标,这样,在添加节点或者册l除子树改变=又树的高度的时候,树的高度就能白造应屏幕。八、指导教师审核意见：指导教师签名：2015年6月25日