数据结构课程设计二叉树遍历C++语言概论.doc

淮阴工学院实践报告 数据结构课程设计 设计题目： 二叉树遍历 系 别： 计算机工程学院 专 业： 软件工程 班 级： 软件1111 学生姓名: 周淼 学 号: 1111315217 起止日期: 2012年12月24日~2012年12月30日 指导教师： 寇海洲 摘要： 现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希望通过课程设计来提高对数据的处理能力，促进对数据结构课程的理解，在日后面向对象的程序设计中科学的规划数据结构。在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。 关键词：二叉树建立，递归与非递归，遍历，栈，队列 编号： 47 淮阴工学院 软件工程 专业 数据结构课程设计答辩记录 课题名称： 二叉树的算法 班 级 软件1111 学 号 1111315217 姓 名 周淼 答 辩 记 录 问题1：课题中涉及到哪些数据结构和算法？ 答： 1）数组，二叉树，栈，队列，线性表 2）二叉树的中序、前序、后序的递归、非递归遍历算法，层次序遍历非递归算法，栈、队列的实现算法 问题2：课题研究和设计中的关键技术是什么？ 答：关键技术是二叉树的建立，以及栈结构、队列的算法实现 问题3：课题的主要功能和模块有哪些？ 答：1）主要功能：根据数据建立二叉树，实现二叉树的中序、前序、后序遍历 2）模块：栈的应用，队列结构的应用，二叉树的操作 问题4：课题在实现过程中遇到的主要难点有哪些？ 答：遍历二叉树过程中栈结构以及队列的使用 问题5：课题中未能实现的功能有哪些？ 答：以树形结构输出完全二叉树 记录人：寇海洲 2012 年 12 月 28日 目 录 1需求分析 5 1.1二叉树与树结构 5 1.2面向对象的程序设计 5 1.3二叉树遍历的应用 5 1.4软件运行环境：Visual C++ 6.0版本 5 2概要设计 6 2.1 总体功能结构 6 2.2数据结构部分设计 6 2.2.1结点结构 6 2.2.2 二叉树结构 7 3详细设计 12 3.1建立二叉树 12 3.1.1功能描述 12 3.1.2算法原理 12 3.1.3 具体程序 12 3.2 前序遍历 13 3.2.1 功能原理 13 3.2.2 算法原理 13 3.2.3 具体程序 13 3.3 中序遍历 14 3.3.1 功能原理 14 3.3.2 算法原理 14 3.3.3 具体程序 14 3.4 后序遍历 15 3.4.1功能原理 15 3.4.2 算法原理 15 3.4.3 具体程序 16 3.5层次序非递归遍历 17 3.5.1 功能原理 17 3.5.2 算法原理 17 3.5.3 具体程序 17 3.6 栈结构 18 3.6.1 功能原理 18 3.6.2算法原理 18 3.6.3 具体程序 18 3.7 队列结构 19 3.7.1 功能原理 19 3.7.2 算法原理 19 3.7.3 具体程序 19 4调试与操作说明 20 致 谢 23 参考文献 24 附录： 25  1需求分析 1.1二叉树与树结构 树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。 一个好的二叉树遍历算法应包含以下功能： 1）以递归和非递归方法建立二叉树或完全二叉树； 2）实现二叉树的前序遍历、中序遍历、后序遍历； 3）每种遍历算法皆以递归和非递归方法实现； 4）在具体实现时应用其他数据结构类型对数据进行操作，如：栈，队列，数组。 1.2面向对象的程序设计 在面向对象的程序设计中，模板的使用很普遍，因此，如何在程序设计中使用模板使得方法的实现与定义分开，程序模块化，既方便了程序设计者，又为程序的后期维护带来便利。 1.3二叉树遍历的应用 当数据以数组或文档形式存储在内存时