最终数据结构报告

《最终数据结构报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：二叉树的遍历院（系）：计算机学院专业：网络工程班级：84010202学号：2008040102040姓名：王迪指导教师：郑志勇1课程设计介绍11.1课程设计内容11.2课程设计耍求12课程设计原理22」课设题目粗略分析22.2原理图介绍22.2.1功能模块图22.2.2流程图分析32.2.3二叉树创建模块52.2.4前序遍历模块52.2.5中序遍历模块72.2.6层序遍历模块83数据结构分析103.1存储结构103.2算法描述104调试与分析144.1调试过程144.2程序执行过程14参考文献16录

2、（关键部分程序清单）1课程设计介绍1.1课程设计内容内容：从键盘输入二叉树的二叉链结构，并实现二叉树的前序和中序以及层次遍历。1.2课程设计要求要求：(1)前序和中序采用非递归算法实现；(2)层次遍历借助队列来实现；(3)要能够形象方便地观察所构造二叉树的图形结构。2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为五大模块。前四个模块相互独立，没有嵌套调用的情况，第五个模块调用前儿个模块的函数。下面是五个模块的大体分析：(1)二叉树建立模块。该模块主要实现的功能是：输入二叉树的前序屮序序列，构造出一棵二叉树；(2)非递归前序遍历模块。该模块的主要功能

3、是：借助栈来实现对该二叉树的非递归前序遍历；(3)非递归中序遍历模块。该模块主要功能同样是借助栈来实现对该二叉树的中序遍历；(4)层次遍历模块。该模块主要是借助队列来实现对所建二叉树的层次遍历;(5)主函数模块。该模块主要功能是：通过输入二叉树的前序中序序列并调用前面模块的函数实现整个程序。2.2原理图介绍本程序主要分为一个主函数模块和四个子函数模块，主函数调用子函数，实现对二叉树的建立和遍历功能，以下为各模块的详细分析。2.2.1功能模块图本程序主要分为五个模块：分别为主函数模块，二叉树建立模块，前序遍历模块，中序遍历模块，层次遍历模块。功能模块图如图2」所示。2课程

4、设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为五大模块。前四个模块相互独立，没有嵌套调用的情况，第五个模块调用前儿个模块的函数。下面是五个模块的大体分析：(1)二叉树建立模块。该模块主要实现的功能是：输入二叉树的前序屮序序列，构造出一棵二叉树；(2)非递归前序遍历模块。该模块的主要功能是：借助栈来实现对该二叉树的非递归前序遍历；(3)非递归中序遍历模块。该模块主要功能同样是借助栈来实现对该二叉树的中序遍历；(4)层次遍历模块。该模块主要是借助队列来实现对所建二叉树的层次遍历;(5)主函数模块。该模块主要功能是：通过输入二叉树的前序中序序列并调用前面模块

5、的函数实现整个程序。2.2原理图介绍本程序主要分为一个主函数模块和四个子函数模块，主函数调用子函数，实现对二叉树的建立和遍历功能，以下为各模块的详细分析。2.2.1功能模块图本程序主要分为五个模块：分别为主函数模块，二叉树建立模块，前序遍历模块，中序遍历模块，层次遍历模块。功能模块图如图2」所示。图2.1功能模块图2.2.2流程图分析木程序中主函数分别调用了四个函数，首先调用CreatBT()函数，完成二叉树的创建，然后调用preO「derUNre()函数，对所建二叉树进行非递归前序遍历,并输出遍历结果，然后调用inOi・derUNre()函数，对所建二叉树进行非递归中

6、序遍历并输出结果。最后调用levelOrder()函数，借助队列来实现对二叉树的层序遍历,并输出遍历结果。主函数模块实现了主函数控制整个程序的运行，控制输入操作,通过主函数模块分别调用各个模块，实现各项功能，主模块流程如图2.2所示。2.2.3二叉树创建模块该模块主要从键盘输入二叉树的前序中序序列，递归调用节点构造函数BinaryNodeO，根据输入的序列，构造岀一棵二叉树。2.2.4前序遍历模块该模块主要借助栈来实现对二叉树的非递归先序遍历，首先将根节点存入栈中，若栈中元素非空，则将栈中元素出栈并对其进行访问，然后将其左孩子节点存入栈屮，直到指针指向空，然后将右孩子节

7、点存入栈屮，若栈非空则对其进行访问，输出结果，直到栈中元素达到空为止。具体流程图如图2.3所示。开始V图23前序遍历流程图2.2.5中序遍历模块该模块与前序遍历模块相似，主要借助指针P和利用栈来实现对二叉树的非递归中序遍历，流程图如图2.4所示。（开始结束2.2.6层序遍历模块按照要求，该模块应该借助队列来实现对二叉树的层次遍历，将该根节点存入队列中若队列元素非空，则队中元素出队并访问出队元素，若左孩子节点非空,则将其存入队列中，否则判断其右孩子节点，若同样非空，则将右孩子节点存入队中，然后使队屮元素出队，对出队元素进行访问，直到队列为