数据结构课程设计二叉树遍历c++语言

《数据结构课程设计二叉树遍历c++语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、淮阴工学院实践报告数据结构课程设计设计题目：二叉树遍历系别：计算机工程学院专业：软件工程班级：软件1111学生姓名:周淼学号:1111315217起止日期:2012年12月24日~2012年12月30日指导教师：寇海洲41摘要：现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希

2、望通过课程设计来提高对数据的处理能力，促进对数据结构课程的理解，在日后面向对象的程序设计中科学的规划数据结构。在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。关键词：二叉树建立，递归与非递归，遍历，栈，队列41编号：47淮阴工学院软件工程专业数据结构课程设计答辩记录课题名称：二叉树的算法班级软件1111学号

3、1111315217姓名周淼答辩记录问题1：课题中涉及到哪些数据结构和算法？答：1）数组，二叉树，栈，队列，线性表2）二叉树的中序、前序、后序的递归、非递归遍历算法，层次序遍历非递归算法，栈、队列的实现算法问题2：课题研究和设计中的关键技术是什么？答：关键技术是二叉树的建立，以及栈结构、队列的算法实现问题3：课题的主要功能和模块有哪些？答：1）主要功能：根据数据建立二叉树，实现二叉树的中序、前序、后序遍历2）模块：栈的应用，队列结构的应用，二叉树的操作问题4：课题在实现过程中遇到的主要难点有哪些？答：遍历二叉

4、树过程中栈结构以及队列的使用问题5：课题中未能实现的功能有哪些？答：以树形结构输出完全二叉树记录人：寇海洲2012年12月28日41目录1需求分析51.1二叉树与树结构51.2面向对象的程序设计51.3二叉树遍历的应用51.4软件运行环境：VisualC++6.0版本52概要设计62.1总体功能结构62.2数据结构部分设计62.2.1结点结构62.2.2二叉树结构73详细设计123.1建立二叉树123.1.1功能描述123.1.2算法原理123.1.3具体程序123.2前序遍历133.2.1功能原理133.2

5、.2算法原理133.2.3具体程序133.3中序遍历143.3.1功能原理143.3.2算法原理143.3.3具体程序143.4后序遍历153.4.1功能原理153.4.2算法原理153.4.3具体程序163.5层次序非递归遍历173.5.1功能原理173.5.2算法原理173.5.3具体程序173.6栈结构183.6.1功能原理183.6.2算法原理183.6.3具体程序183.7队列结构193.7.1功能原理193.7.2算法原理19413.7.3具体程序194调试与操作说明20致谢23参考文献24附录：

6、25411需求分析1.1二叉树与树结构树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。一个好的二叉树遍历算法应包含以下功能：1）以递归和非递归方法建立二叉树或完全二叉树；2）实现二叉树的前序遍历、中序遍历、后序遍历；3）每种遍历算法皆以递归和非递归方法实现；4）在具体实现时应用其他数据结构类型对数据进行操作，如：栈，队列，数组。1.2面向对象的程序设计在面向对象的程序设计中，模板的使用很普遍，因此，如何在程序

7、设计中使用模板使得方法的实现与定义分开，程序模块化，既方便了程序设计者，又为程序的后期维护带来便利。1.3二叉树遍历的应用当数据以数组或文档形式存储在内存时，其数据之间虽有逻辑联系，却过于分散，因此，建立二叉树以存储数据并且遍历该二叉树，可以从逻辑上理顺数据之间的关系，使得原本分数的数据排列的有序且可靠。一个好的二叉树应用算法其空间复杂度与时间复杂度必然最低，这样给程序带来时间和空间上的极大优化。1.4软件运行环境：VisualC++6.0版本412概要设计2.1总体功能结构二叉树的遍历，主要包含以下功能：1

8、）建立二叉树：递归方法、非递归方法2）中序遍历：递归方法、非递归方法3）前序遍历：递归方法、非递归方法4）后序遍历：递归方法、非递归方法5）栈结构使用：遍历时输入临时变量以保存6）队列结构使用：完全二叉树遍历时用以存储数据2.2数据结构部分设计2.2.1结点结构二叉树结点结构中包数据域（data），指针域（*leftChild，*rightChild）。结点结构的代码如下：structBinTree