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

《数据结构》课程设计报告
题目二叉树的遍历
学生姓名
学号
专业班级
指导老师
设计日期
指导老师评阅意见:
评阅成绩:
签名:
目录
题目及要求
……………………………………………1
二、设计的作用目的
……………………………………………3
三、具体设计
……………………………………………7
问题及解决方法
……………………………………………17
程序结果集分析
……………………………………………19
心得体会
……………………………………………20
参考文献
……………………………………………20
一、问题定义

通过本项课程设计,培养学生独立思考、综合运用所学有关相应知识的能力,使学生巩固《数据结构》课程学****的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,闯过理论与实践相结合的难关;
为了培养学生综合运用所学知识、独立分析和解决实际问题的能力,培养创
意识和创新能力,使学生获得科学研究的基础训练。
为后续各门计算机课程的学****和毕业设计打下坚实基础。
同时,可以利用这次机会来检验自己的c/c++/数据结构水平,提高自己的写作水平,锻炼自己的动手能力。

收集资料,全面分析课题,分解问题,形成整体编程思路;
深入分析各个小问题,编写各部分程序模块;
对于设计中用到的关键函数,要联系问题进行具体介绍;
上机调试,确保程序能正确运行;
完成设计报告,并进行答辩。

增强自己的动手能力,熟悉和掌握二叉树各种遍历的算法,以及栈和队列在遍历二叉树中的应用,增强自己的调试程序和测试程序的能力。


(前、中、后)

(前、中、后)


⑴二叉树的递归定义:
二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
⑵二叉树的五种基本形态
二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。二叉树的五种基本形态如下图所示。 

⑶二叉树不是树的特例
①二叉树与无序树不同:
二叉树中,每个结点最多只能有两棵子树,并且有左右之分。
二叉树并非是树的特殊情形,它们是两种不同的数据结构。
②二叉树与度数为2的有序树不同:
在有序树中,虽然一个结点的孩子之间是有左右次序的,但是若该结点只有一个孩子,就无须区分其左右次序。而在二叉树中,即使是一个孩子也有左右之分。 
【例】下图中(a)和(b)是两棵不同的二叉树,它们同右图中的普通树(作为有序树或无序树)很相似,但却不等同于这棵普通树。若将这三棵树均看做普通树,则它们就是相同的了。
⑷二叉树的遍历:
二叉树是数据结构中一种非常重要的非线形结构。二叉树的一个重要运算是按深度遍历二叉树,即前序遍历和后序遍历。用程序实现图形演示这三种遍历二叉树的过程。
二叉树是一种特殊的树,这种特殊不仅仅在于其分支最多为2以及其它特征,一个最重要的特殊之处是在于:二叉树是有序的!即:二叉树的左右孩子是不可交换的,如果交换了就成了另外一棵二叉树,这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是,对于普通的双分支树而言,不具有这种性质。
二叉树的遍历算法有三种:先序,中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法,理解其执行的实际步骤,并且应该熟练掌握三种遍历的非递归算法。
:
⑴遍历方案:
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
①访问结点本身(N),
②遍历该结点的左子树(L),
③遍历该结点的右子树(R)。
以上三种操作有六种执行次序:
NLR、LNR、LRN、NRL、RNL、RLN。
注意:
前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。
⑵三种遍历的命名:
根据访问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意:
由于被