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

贵州师范大学
数据结构课程设计报告
(二叉树的遍历)
系别: 计算机工程系
班级: 11计应
学号:
姓名:
指导老师:
完成日期: 2012/6/27
目录
、要求、内容、功能 1
1
二、课程设计的基本要求 1
三、课程设计内容 2
四、实现什么功能 2
3
3
4
6
9
9
15
16
17
、要求、内容、功能

《数据结构》主要介绍一些最常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程。
学****数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的:
,具备初步的独立分析和设计能力;
、系统设计、程序编码、测试等基本方法和技能;
;
,培养软件工作者所应具备的科学的工作方法和作风。
二、课程设计的基本要求
1. 问题分析和任务定义:
根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么?(而不是怎么做?)限制条件是什么?
2. 逻辑设计:
对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调用关系图;
3. 详细设计:
定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调
一试,抽象数据类型的实现尽可能做到数据封装,基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精,写出数据存储结构的类型定义,写出函数形式的算法框架;
4. 程序编码:
把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言,使程序中逻辑概念清楚;
5. 程序调试与测试:
采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。调试正确后,认真整理源程序及其注释,形成案例格式和风格良好的源程序清单和结果;
三、课程设计内容
二叉树遍历算法集成
功能要求:
界面友好,易与操作。可采用菜单或其它人机对话方式进行选择。
实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法。
演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。
在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法;
四、实现什么功能
该程序实现二叉树的遍历
二叉树的遍历是指按照一定的规则访问二叉树的各个结点,使每个结点都被且只被访问一次。二叉树遍历的实质是将非线性结构的数据线性化的过程,二叉树的遍历是二叉树的一个重要操作,许多关于二叉树的操作都是基于二叉树的遍历,例如查找二叉树中具有某种特征的结点或对二叉树中得全部结点逐一进行处理等操作。二叉树的遍历根据访问的规则不同,可以分为先序遍历、中序遍历、后序遍历、层次遍历四种访问方式。

定义二叉树node
并
建立二叉树chuangjian
二叉树的递归算法
二叉树的层次遍历算法
二叉树的非递归算法
先序遍历
xianxu
中序遍历
zhongxu
后序遍历
Houxu
先序遍历
fdgxx
中序遍历
fdgzx
后序遍历
fdghx
层次遍历
cengci
主函数
Main


二叉树是有限个结点的集合,这个集合或者是空集,或者一个根结点和两棵不相交的二叉树组成其中一棵叫做左子树,另一棵叫做右子树。
思想:
递归
先序:是按照根左右的方式进行访问
中序:是按照左根右的方式进行访问
后序:是按照左右根的方式进行访问
非递归
先序:是按照根左右的方式进行