资源描述：
《数据结构课程设计报告_遍历二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、遍历二叉树XXXX大学《数据结构》课程设计报告课题名称:遍历二叉树系（院）:专业:班级:组员姓名:学号:指导教师:开课时间:学年学期遍历二叉树摘要树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.针对这样的问题,我选择了二叉树的遍历作为我的课程设计主题,编写程序,实现对二叉树的遍历.在本次课程设计中,二叉树的建立使用了递归算法；在前序、中序和后续遍历
2、的算法中则同时使用了递归与非递归的算法,即在这些遍历算法的实现中使用了栈结构与队列结构,提供了6种不同的遍历方式,供使用者选择.同时,该程序具有输出层序遍历的功能,层序遍历模块使用了非递归算法.该程序基本实现了对二叉树的遍历,对于递归与非递归算法,我们应从实际应用中体验这些算法的优越性.关键词:层次关系,二叉树建立,递归与非递归,遍历,栈,队列遍历二叉树目录一、问题描述1二、需求分析12.1主功能模块12.2创建树模块12.3遍历树模块1三、概要设计23.1主界面设计思想流程图23.2.创建二叉树23.2.1二叉树创建的思想23.2.2二叉树创建的
3、算法流程图23.3.先序递归遍历33.3.1先序递归遍历思想33.3.2先序递归遍历的算法流程图33.4.中序递归遍历33.4.1中序递归遍历思想33.4.2中序递归遍历的算法流程图43.5.后序递归遍历43.5.1后序递归遍历思想43.5.2后序递归遍历的算法流程图53.6.先序非递归遍历53.6.1先序非递归遍历思想53.6.2先序非递归遍历的算法流程图63.7.中序非递归遍历63.7.1中序非递归遍历思想63.7.2中序非递归遍历的算法流程图73.8.后序非递归遍历73.8.1后序非递归遍历思想73.8.2后序非递归遍历的算法流程图83.9.
4、层序非递归遍历83.9.1层序非递归遍历思想83.9.2层序非递归遍历的算法流程图9四、详细设计104.1界面设计104.2.详细代码分析114.2.1主模块114.2.2创建树模块124.2.3遍历树模块13五、调试分析135.1.调试结果135.1.1实验数据135.1.2创建树界面145.1.3输出结果界面14遍历二叉树5.2.算法分析165.2.1时间复杂度165.2.2空间复杂度165.3.程序的不足165.3.1程序不足之处16六、心得体会17七、参考文献17遍历二叉树一、问题描述建立二叉树,层序、先序、中序、后序遍历.(用递归或非递归
5、的方法都可以)要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数.二、需求分析在现实世界层次化的数据模型中,数据与数据之间的关系纷繁复杂.其中很多关系无法使用简单的线性结构表示清楚,比如祖先与后代的关系、整体与部分的关系等.于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树.树形结构的具体形式有很多种,其中最常用的就是二叉树.而二叉树的多层次遍历遍历则是二叉树的重要内容.本程序用MicrosoftV
6、isualC++6.0编写,可以实现对二叉树的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历.2.1主功能模块通过合理的界面设计,根据提示信息,使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作.界面美观,人性化,程序智能,安全性高.2.2创建树模块当进入程序运行界面后,根据提示输入需要建立的二叉树,按照先序次序输入各个结点的值,完成二叉树的建立.2.3遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作,并输出各遍历序列.22遍历二叉树
7、一、概要设计3.1主界面设计思想流程图3.2.创建二叉树3.2.1二叉树创建的思想(1)定义二叉树结点值的类型为字符型.(2)结点个数不超过10个.(3)按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树.相关函数如下:voidCreateBiTree(BiTree&T)3.2.2二叉树创建的算法流程图开始创建二叉树结束22遍历二叉树3.3.先序递归遍历3.3.1先序递归遍历思想若二叉树为空,则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树.相关函数如下:voidPreOrderTraverse(BiTreeT)3.
8、3.2先序递归遍历的算法流程图开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历右子树YN3.4.
