最终数据结构报告.docVIP

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：二叉树的遍历 院（系）：计算机学院 专 业：网络工程 班 级学 号：2008040102040 姓 名：王迪 指导教师：郑志勇 目 录 1 课程设计介绍 1 1.1 课程设计内容 1 1.2 课程设计要求 1 2 课程设计原理 2 2.1 课设题目粗略分析 2 2.2 原理图介绍 2 2.2.1 功能模块图 2 2.2.2 流程图分析 3 2.2.3二叉树创建模块 5 2.2.4前序遍历模块 5 2.2.5中序遍历模块 7 2.2.6层序遍历模块 8 3 数据结构分析 10 3.1 存储结构 10 3.2 算法描述 10 4 调试与分析 14 4.1 调试过程 14 4. 2程序执行过程 14 参考文献 16 附 录（关键部分程序清单） 17 1 课程设计介绍 1.1 课程设计内容 内容：从键盘输入二叉树的二叉链结构，并实现二叉树的前序和中序以及层次遍历。 1.2 课程设计要求 要求：（1）前序和中序采用非递归算法实现； （2）层次遍历借助队列来实现； （3）要能够形象方便地观察所构造二叉树的图形结构。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为五大模块。前四个模块相互独立，没有嵌套调用的情况，第五个模块调用前几个模块的函数。下面是五个模块的大体分析： （1）二叉树建立模块。该模块主要实现的功能是：输入二叉树的前序中序序列，构造出一棵二叉树； （2）.2 原理图介绍 本程序主要分为一个主函数模块和四个子函数模块，主函数调用子函数，实现对二叉树的建立和遍历功能，以下为各模块的详细分析。 2.2.1 功能模块图 本程序主要分为五个模块：分别为主函数模块，二叉树建立模块，前序遍历模块，中序遍历模块，层次遍历模块。功能模块图如图2.1所示。 图2.1功能模块图 2.2.2 流程图分析 本程序中主函数分别调用了四个函数，首先调用CreatBT（）函数，完成二叉树的创建，然后调用preOrderUNre()函数，对所建二叉树进行非递归前序遍历，并输出遍历结果，然后调用inOrderUNre()函数，对所建二叉树进行非递归中序遍历并输出结果。最后调用levelOrder()函数，借助队列来实现对二叉树的层序遍历，并输出遍历结果。主函数模块实现了主函数控制整个程序的运行，控制输入操作，通过主函数模块分别调用各个模块，实现各项功能，主模块流程如图2.2所示。 图2.2主函数流程图 2.2.3二叉树创建模块 该模块主要从键盘输入二叉树的前序中序序列，递归调用节点构造函数BinaryNode()，根据输入的序列，构造出一棵二叉树。 2.2.4前序遍历模块 该模块主要借助栈来实现对二叉树的非递归先序遍历，首先将根节点存入栈中，若栈中元素非空，则将栈中元素出栈并对其进行访问，然后将其左孩子节点存入栈中，直到指针指向空，然后将右孩子节点存入栈中，若栈非空则对其进行访问，输出结果，直到栈中元素达到空为止。具体流程图如图2.3所示。 图2.3前序遍历流程图 2.2.5中序遍历模块 该模块与前序遍历模块相似，主要借助指针P和利用栈来实现对二叉树的非递归中序遍历，流程图如图2.4所示。 图2.4中序遍历模块流程图 2.2.6层序遍历模块 按照要求，该模块应该借助队列来实现对二叉树的层次遍历，将该根节点存入队列中若队列元素非空，则队中元素出队并访问出队元素，若左孩子节点非空，则将其存入队列中，否则判断其右孩子节点，若同样非空，则将右孩子节点存入队中，然后使队中元素出队，对出队元素进行访问，直到队列为空。具体流程如图2.5所示。 图2.5层序遍历模块图 3 数据结构分析 3.1 存储结构 本程序采用链式存储结构，具体代码如下： BinaryNode* leftChild; BinaryNode* rightChild; char name; public: BinaryNode(char a) { name=a; leftChild=NULL; rightChild=NULL; } 3.2 算法描述 （1）输入二叉树的前序中序序列，构建一个二叉树 ，具体代码如下： BinaryNode * CreateBT (string pres, string ins ) //利用前序中序建立树 { int inpos; BinaryNode * temp; string prestemp, instemp