题目3_树的运用1_报告
- 格式：docx
- 大小：194.54 KB
- 文档页数：37
理学院
课程设计说明书
课 程 名 称: 数据结构与算法A设计实践
课 程 代 码: 6015059
题 目 三: 树的运用1
年级/专业/班: 2013/信科/2班
学 生 姓 名: 冯金慧
学 号: 3120130902209
开 始 时 间: 2015 年 12 月 28 日
完 成 时 间: 2016 年 01 月 10 日
课程设计成绩：
学习态度及平时成绩（30） 技术水平与实际能力（20）
创新（5） 说明书撰写质量（45） 总 分（100）
指导教师签名： 年 月 日
西华大学理学院课程设计说明书
数据结构与算法A设计实践任务书
学院名称： 理学院 课程代码：_6015059________
专业： 信科 年级： 2012
一、 设计题目
树的应用1（限最多1人完成）
二、主要内容
完成二叉树的建立、遍历，比较各算法的效率
三、具体要求及提交的材料
（1）建立一二叉树
（2）实现二叉树的四种遍历，先序、中序、后序遍历，要求三种遍历分别使用递归和非递归实现
（3）实现二叉树的层次遍历
（4）比较以上各遍历方法的运行效率测试数据及测试结果请在上交的资料中写明；必须上机调试通过,按《数据结构课程设计大纲》中的要求完成课程设计报告格式。
设计结束后，每个学生必须上交的材料有：
1 《课程设计报告》打印稿一份 2．课程设计的源代码电子文档一份
四、主要技术路线提示
可参考教材相应现成算法实现建树和遍历；在程序中插入记录时刻的代码。计算运算具体时间可比较各算法的效率。
五、进度安排
共计两周时间，建议进度安排如下：
1． 选题，应该在上机实验之前完成 2. 需求分析、概要设计可分配4学时完成
2． 详细设计可分配4学时 4. 调试和分析可分配10学时。
2学时的机动，可提前安排部分提前结束任务的学生答辩
六、 推荐参考资料
1. 冯博琴 等编著，《软件技术基础》（修改版），西安交通大学出版社，1997
2. 严蔚敏 等著，《数据结构》，清华大学出版社，2003
3. 李芸芳 等著，《软件技术基础》（第二版），清华大学出版社，2000
4. 徐孝凯 等著，《数据结构（C语言描述）》，清华大学出版社，2004
指导教师 签名日期 年 月 日
系 主 任 审核日期 年 月 日 西华大学理学院课程设计说明书
目 录
摘 要 ................................................................... 1
2 系统分析 ................................................................ 4
1功能需求 ............................................................. 4
2.1.1总体要求 ..................................................... 5
2.2 数据需求 ....................................................... 5
3、详细设计与实现 ......................................................... 6
3.1设计思路 .............................................................. 6
3.2详细编码 ........................................................... 6
4．系统测试和结果分析 .................................................... 16
4.1设计测试数据 ...................................................... 16
4.2调试的详细过程 .................................................... 16
5、算法效率的分析 ........................................................ 20
5.1 时间复杂度 ....................................................... 20
5.2空间复杂度 ........................................................ 21
总 结 .................................................................. 22
致 谢 ................................................................... 23
附 录 .................................................................... 25 树的运用1
1 摘 要
在现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树。树形结构的具体形式有很多种，其中最常用的就是二叉树。在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。
对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。
本程序用VS2010环境编写，基于二叉树的递归定义，以及遍历规则，本次课程实践也采用的是先序遍历的规则进行建树以及用递归和非递归的方式进行二叉树的遍历。可以实现对二叉树的创建，采用递归和非递归两种方式分别进行先序、中序、后序，还可以进行层次遍历。最后还对各个算法的时间效率的加以分析，得出结论。
关键词：二叉树，层次遍历，递归遍历，时间效率 西华大学理学院课程设计说明书
2 1 引 言
1. 1问题的提出
首先，需要弄清楚选择哪种方式创建一棵二叉树；其次，该二叉树如何进行存储有利于后序的操作，最后，对所创建的二叉树如何实现先中后的递归和非递归遍历以及层次遍历，并输出遍历的结果
1.2 C语言
C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。
1.3 C语言发展过程
1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。
1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。
1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming
Language》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。
1.4任务与分析
任务主要分为以下几个板块：
（1）建立二叉树结构
建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。
二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。 树的运用1
3 （2）输入二叉树元素
输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。
（3）先序递归和非递归遍历二叉树
当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树，非递归则需要使用栈来实现。
（4）中序递归和非递归遍历二叉树
当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树，非递归则需要使用栈来实现。
（5）后序递归和非递归遍历二叉树
当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
（6）层次遍历
层次遍历则需要执行以下操作：从上到下，从左到右进行遍历。
（7）主程序
需列出各个函数，然后进行函数调用。最后，比较以上各遍历方法的运行效率。
分析：
首先，二叉树创建的方法比较多，结合这学期学习的数据结构这门课程，我选择了先序创建二叉树，其次，对二叉树采用不同的方式进行遍历，想到了将不同的遍历方法依次分块写成函数，需要采用哪种方式遍历二叉树时仅需要调用相应的函数就行了，这样把一个大问题分成若干个小问题，解决起来就简单方便的多了。 西华大学理学院课程设计说明书
4
2 系统分析
1功能需求
此课题是研究创建二叉树，并用不同的方式对二叉树进行遍历的问题，首先需要创建一棵二叉树，才能继续下一步的运用各种不同的遍历方式对树进行遍历。然后将几种不同的遍历方式各自分成一个子快，编写出相应的7个函数（先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序遍历、后序非递归遍历、层次遍历），然后在主程序里面提示各个选项对相应的功能，用户输入相应的操作数，分别调用不同的函数，打印出相应的遍历顺序。因此，实际需要设计的任务就是创建二叉树，以及不同遍历二叉树方法的函数编写，为了直观和方便，画出流程图如下图1：
图1 程序总的流程图
树的运用
先序非递归遍历 中序非递归遍历 后序非递归遍历 先序递归遍历 中序递归遍历 后序递归遍历 层次遍历
