数据结构课程设计报告--二叉树的遍历

《数据结构课程设计报告--二叉树的遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、题，编写各部分程序模块；③对于设计中用到的关键函数，要联系问题进行具体介绍；④上机调试，确保程序能正确运行；⑤完成设计报告，并进行答辩。3．课题意义增强自己的动手能力，熟悉和掌握二叉树各种遍历的算法，以及栈和队列在遍历二叉树中的应用，增强自己的调试程序和测试程序的能力。4．课题内容1.创建二叉树2.二叉树的递归遍历算法（前、中、后）3.二叉树的层序遍历算法4.二叉树的非递归遍历算法（前、中、后）5.退出5．课题详细设计⑴二叉树的递归定义：二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及

4、两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。⑵二叉树的五种基本形态二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。二叉树的五种基本形态如下图所示。 ⑶二叉树不是树的特例①二叉树与无序树不同：二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树并非是树的特殊情形，它们是两种不同的数据结构。②二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 【例】下图中(a)和(b)是两棵不同的

5、二叉树，它们同右图中的普通树(作为有序树或无序树)很相似，但却不等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。⑷二叉树的遍历：二叉树是数据结构中一种非常重要的非线形结构。二叉树的一个重要运算是按深度遍历二叉树，即前序遍历和后序遍历。用程序实现图形演示这三种遍历二叉树的过程。二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通

6、的双分支树而言，不具有这种性质。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。2.总体设计思想：⑴遍历方案：从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：①访问结点本身(N)，②遍历该结点的左子树(L)，③遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意

7、：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。⑵三种遍历的命名：根据访问结点操作发生位置命名：①NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。②LNR：中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间)。③LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtlee)和R(Rightsubtre

8、e)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。⑶遍历二叉树的执行踪迹：   三种递归遍历算法的搜索路线相同（如下图虚线所示）。具体线路