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

贵州师范大学 数据结构课程设计报告 ： 班 级： 学 号： 姓 名： 指导老师： 完成日期： 2012/6/27  目录 一．课程设计的目的、要求、内容、功能 1 一．课程设计的目的 1 二、课程设计的基本要求 1 三、课程设计内容 2 四、实现什么功能 2 二．基本算法的原理 3 一．流程图 3 二．思想 4 三．测试数据 6 四．源程序及系统文件使用说明 9 一．源程序 9 二．定义和关键函数 15 五．心得体会 16 六．教师点评 17 一．课程设计的目的、要求、内容、功能 一．课程设计的目的 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 问题分析和任务定义： 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2. 逻辑设计： 对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图； 3. 详细设计： 定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调一试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； 4. 程序编码： 把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5. 程序调试与测试： 采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成案例格式和风格良好的源程序清单和结果； 三、课程设计内容 二叉树遍历算法集成 功能要求： 界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。 实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法。 演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 四、实现什么功能 该程序实现二叉树的遍历 二叉树的遍历是指按照一定的规则访问二叉树的各个结点，使每个结点都被且只被访问一次。二叉树遍历的实质是将非线性结构的数据线性化的过程，二叉树的遍历是二叉树的一个重要操作，许多关于二叉树的操作都是基于二叉树的遍历，例如查找二叉树中具有某种特征的结点或对二叉树中得全部结点逐一进行处理等操作。二叉树的遍历根据访问的规则不同，可以分为先序遍历、中序遍历、后序遍历、层次遍历四种访问方式。 二．基本算法的原理 一．流程图 二．思想 二叉树是有限个结点的集合，这个集合或者是空集，或者一个根结点和两棵不相交的二叉树组成其中一棵叫做左子树，另一棵叫做右子树。 思想： 递归 先序：是按照根左右的方式进行访问 中序：是按照左根右的方式进行访问 后序：是按照左右根的方式进行访问 非递归 先序：是按照根左右的方式进行访问 p是要遍历树的根指针，若 != NULL 对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。 方法1：访问-data后，将入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历的右子树。 方法2：访问-data后，将-rchi