数据结构课程设计报告_遍历二叉树.doc

遍历二叉树XXXX大学 数据结构课程设计 报 告课题名称: 遍历二叉树 系 （院）: 专 业: 班 级: 组员姓名: 学 号: 指导教师: 开课时间: 学年 学期摘要树结构在客观世界中广泛存在, 如人类社会的族谱和各种社会组织机构都可用树形象表示. 树在计算机领域中也得到广泛应用, 如在编译源程序时, 可用树表示源程序的语法结构. 又如在数据库系统中, 树型结构也是信息的重要组织形式之一. 一切具有层次关系的问题都可用树来描述. 针对这样的问题, 我选择了二叉树的遍历作为我的课程设计主题, 编写程序, 实现对二叉树的遍历. 在本次课程设计中, 二叉树的建立使用了递归算法；在前序、中序和后续遍历的算法中则同时使用了递归与非递归的算法, 即在这些遍历算法的实现中使用了栈结构与队列结构, 提供了6种不同的遍历方式, 供使用者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使用了非递归算法. 该程序基本实现了对二叉树的遍历, 对于递归与非递归算法, 我们应从实际应用中体验这些算法的优越性. 关键词: 层次关系, 二叉树建立, 递归与非递归, 遍历, 栈, 队列目 录一、问题描述1二、需求分析12.1主功能模块12.2创建树模块12.3遍历树模块1三、概要设计23.1主界面设计思想流程图23.2. 创建二叉树23.2.1二叉树创建的思想23.2.2二叉树创建的算法流程图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.层序非递归遍历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输出结果界面145.2.算法分析165.2.1时间复杂度165.2.2空间复杂度165.3.程序的不足165.3.1程序不足之处16六、心得体会17七、参考文献17一、 问题描述建立二叉树, 层序、先序、中序、后序遍历.(用递归或非递归的方法都可以)要求能够输入树的各个结点, 并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数. 二、 需求分析在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系无法使用简单的线性结构表示清楚, 比如祖先与后代的关系、整体与部分的关系等. 于是人们借鉴自然界中树的形象创造了一种强大的非线性结构树. 树形结构的具体形式有很多种, 其中最常用的就是二叉树. 而二叉树的多层次遍历遍历则是二叉树的重要内容. 本程序用Microsoft Visual C+ 6.0编写, 可以实现对二叉树的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历. 2.1主功能模块通过合理的界面设计, 根据提示信息, 使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作. 界面美观, 人性化, 程序智能, 安全性高. 2.2创建树模块当进入程序运行界面后, 根据提示输入需要建立的二叉树, 按照先序次序输入各个结点的值, 完成二叉树的建立. 2.3遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作, 并输出各遍历序列. 三、 概要设计3.1主界面设计思想流程图3.2. 创建二叉树3.2.1二叉树创建的思想(1)定义二叉树结点值的类型为字符型. (2)结点个数不超过10个. (3)按先序次序输入, 构造二叉链表表示的二叉树T, 空格表示空树. 相关函数如下: void CreateBiTree(BiTree &T)3.2.2二叉树创建的算法流程图开始创建二叉树结束3.3.先序递归遍历3.3.1先序递归遍历思想若二叉树为空, 则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树. 相关函数如下: void PreOrderTraverse(BiTree T)3.3.2先序递归遍历的算法流程图开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历右子树YN3.4.中序递归遍历3.4.1中序递归遍历思想若二叉树为空, 则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树. 相关函数如下: void InOrderTraverse(BiTree T)3.4.2中序递归遍历的算法流程图开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN3.5.后序递归遍历3.5.1后序递归遍历思想若二叉树为空, 则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)3.5.2后序递归遍历的算法流程图开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN3.6.先序非递归遍历3.6.1先序非递归遍历思想(1)访问结点的数据域；(2)指针指向p的左孩子结点；(3)从栈中弹出栈顶元素；(4)指针指向p的右孩子结点. 相关函数如下: void NRPreOrder(BiTree bt)3.6.2先序非递归遍历的算法流程图开始申请一个STL栈stack s判断结点是否空输出结点值p-datas.push(p)结点的值变为它的左孩子判断结点是否空p=s.pop()p=p-rchild结束判断栈或结点是否空NYNYN3.7.中序非递归遍历3.7.1中序非递归遍历思想(1)指针指向p的左孩子结点；(2)从栈中弹出栈顶元素；(3)访问结点的数据域；(4)指针指向p的右孩子结点. 相关函数如下: void NRInOrder(BiTree bt)3.7.2中序非递归遍历的算法流程图开始申请一个STL栈stack s判断结点是否空s.push(p)结点的值变为它的左孩子判断结点是否空输出结点值p-datap=s.pop()p=p-rchild结束判断栈或结点是否空NYYNN3.8.后序非递归遍历3.8.1后序非递归遍历思想若二叉树为空, 则空操作；否则引入栈和标记模拟递归工作栈, 初始时栈为空. 相关函数如下: void NRPostOrder(BiTree bt);3.8.2后序非递归遍历的算法流程图开始申请一个STL栈stack s;用一个bool变量flag标记是否访问flag=0 s.push(p)p=p-lchild top+判断标志flag是否为1输出结点的数据p-datap = s.pop()p= p-rchild结束NYYNNYYN判断结点是否空判断栈或结点是否空判断结点是否空3.9.层序非递归遍历3.9.1层序非递归遍历思想(1)访问该元素所指结点. (2)若该元素所指结点的左右孩子结点非空, 则该元素所指结点的左孩子指针和右孩子指针顺序入队. 相关函数如下: void LevelOrderTraverse(BiTree T)3.9.2层序非递归遍历的算法流程图开始申请一个STL队列queue q结束N判断结点是否空Y判断左结点是否空q.push(p-rchild)q.push(p-lchild)判断右结点是否空q.push(root);判断队列是否为空p=q.front()；输出结点值p-data; q.pop()YYNNYN四、 详细设计4.1界面设计图4-1 系统运行主界面图4-2 创建二叉树界面图4-3 二叉树递归遍历界面4.2.详细代码分析4.2.1主模块本模块定义了系统运行主界面的相关内容和相关操作函数, 源代码如下: void main() BiTree T; T=NULL; int select; /cout请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):endl;/ CreateBiTree(T); while(1) coutnn请选择要执行的操作:n; cout1.创建二叉树n; cout2.二叉树的递归遍历算法（前、中、后）n; cout3.二叉树的层次遍历算法n;cout4.二叉树的非递归遍历算法（前、中、后）n; coutselect; switch(select) case 0:return; case 1: cout请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):endl; CreateBiTree(T); break; case 2: if(!T) cout未建立树, 请先建树！; else coutn先序遍历:n; PreOrderTraverse(T); coutn中序遍历:n; InOrderTraverse(T); coutn后序遍历:n; PostOrderTraverse(T); break; case 3: coutn层序遍历:n; LevelOrderTraverse(T); break; case 4: if(!T) cout未建立树, 请先建树！; else coutn先序遍历:n; NRPreOrder(T); coutn中序遍历:n; NRInOrder(T); coutn后序遍历:n; NRPostOrder(T); break; default: cout请确认选择项:n; /end switch /end while4.2.2创建树模块源代码如下: void CreateBiTree(BiTree &T)/按先序次序输入, 构造二叉链表表示的二叉树T, 空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入, 在cin中不能识别空格. if(ch= ) T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); 4.2.3遍历树模块本模块包括了各种遍历二叉树的函数, 源代码如下: void PreOrderTraverse(BiTree T) /二叉树的先序遍历(递归)成员函数声明void InOrderTraverse(BiTree T) /二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse(BiTree T) /二叉树的后序遍历(递归)成员函数声明void LevelOrderTraverse(BiTree T) / 二叉树的层序遍历(非递归)成员函数声明void NRPreOrder(BiTree bt) / 二叉树的先序遍历(非递归)成员函数声明void NRInOrder(BiTree bt) /二叉树的中序遍历(非递归)成员函数声明void NRPostOrder(BiTree bt) /二叉树的后序遍历(非递归)成员函数声明五、 调试分析5.1.调试结果5.1.1实验数据ABCDEFHG这棵树是随机画的, 由数据结构知识, 按照先序次序输入各个节点的值为: ABD#CEG#F#H#(此处#代表空格). 在程序中输入这些节点, 创建树, 如下图: 5.1.2创建树界面图5-1 创建树界面5.1.3输出结果界面输入2, 输出该二叉树递归遍历算法的遍历结果, 结果如下: 输入3, 输出该二叉树层序遍历算法的遍历结果, 结果如下: 输入4, 输出该二叉树非递归遍历算法的遍历结果, 结果如下: 5.2.算法分析5.2.1时间复杂度无论是先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历, 其基本操作是访问二叉树结点. 因此对于n个结点的二叉树, 其时间复杂度均为O(n). 5.2.2空间复杂度对于采用递归的方法遍历二叉树, 即先序递归遍历、中序递归遍历、后序递归遍历, 并不需要辅助空间就能实现对二叉树的遍历, 则空间复杂度为O(1). 对于采用非递归的方法遍历二叉树, 即先序非递归遍历、中序非递归遍历、后序非递归遍历, 所需辅助空间为遍历过程中栈的最大容量, 即树的深度, 一般情况下为 , 则空间复杂度为O( ), 最坏情况下为n, 则空间复杂度也为O(n). 5.3.程序的不足5.3.1程序不足之处(1)创建树模块不够智能化, 自己需要根据给出的二叉树写出节点次序, 输入节点次序运行得到想要的结果. (2)当对该二叉树进行层序非递归遍历时, 不能直接输出该树的逻辑结构图, 不能直观地显示其层次关系. 以下是网络上找的, 他们做的层序遍历就可以直观的看出层次关系. 22六、 心得体会对于选择这个题目, 起初, 没有一点头绪, 经过查阅各种资料和上网查询, 以及多方面的了解, 认识由浅入深, 慢慢的形成一个轮廓. 在课程设计这一期间, 遇见一些重要的问题, 其中的一些小的问题, 通过上网查询和讨论以及询问同学不算太难, 但是非递归遍历算法相对较难, 对于程序理解较差, 在请教一些计算机基础较好同学后对算法的大致运行有了基本的了解. 这一次的课程设计给我们提供了一个既能动手又动脑, 独立实践的机会, 我们就应该紧紧抓住这个机会把我们的所学数据结构课程进一步的巩固和加深, 进一步培养我们的综合能力. 灵活运用各种数据类型组成一个具有系统性的程序. 之前在理论课上的学习, 自己对于二叉树这一块还是蛮感兴趣的, 但是接触之后, 发现非递归这一块还是需要下功夫的. 同时这次的课程设计也让我们知道学习不仅要学份内的东西, 还要多看书拓展自己的知识面. 多一些勤奋, 少一些懒惰. 虽然这次的课程设计大家都有自己各自的题目, 但是组员中有人有问题, 大家都是互相帮忙, 体现出很好的团队精神. 开心的合作, 愉快的交谈, 问题不再迷茫, 一起解决问题, 成功会因合作而发芽, 会因合作而有深意. 最后, 这次实践, 我们应该更能了解我们自己, 自己所学的不深, 需要我们学习的还有很多很多, 成功是百分之九十九的汗水加上百分之一的灵感, 所以我们的路还很长很长, 或许是万里长城, 或许还要翻山越岭, 但是我们都应该永不放弃, 永不言败. 七、 参考文献1 数据结构( C语言版) 严蔚敏、吴伟民编著 清华大学出版社 2009年9月2 C+程序设计教程( 第二版) 钱能编著 清华大学出版社 2005年6月3 C+数据结构原理与经典问题求解 左飞编著 电子工业出版社 2008年6月4 数据结构与算法C+版（第三版）Adam Drozdek编著 郑岩、战晓苏翻译 清华大学出版社 2006年1月完整代码：我们是另外交一份代码的#include iostream.h#include stdlib.h#include stdio.htypedef char ElemType;/定义二叉树结点值的类型为字符型const int MaxLength=10;/结点个数不超过10个typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild;BTNode,* BiTree;void CreateBiTree(BiTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入，在cin中不能识别空格。 if(ch= ) T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); void PreOrderTraverse(BiTree T)/先序遍历 if(T) coutdatalchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T)/中序遍历 if(T) InOrderTraverse(T-lchild); coutdatarchild); void PostOrderTraverse(BiTree T)/后序遍历 if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutdata ; void LevelOrderTraverse(BiTree T)/层序遍历 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根结点入队 Qrear=T; rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; coutdatalchild) /左孩子不为空，入队 Qrear=p-lchild; rear=(rear+1)%MaxLength; if(p-rchild) /右孩子不为空，入队 Qrear=p-rchild; rear=(rear+1)%MaxLength; /非递归的先序遍历算法void NRPreOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) coutdata; stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild; /非递归的中序遍历算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop;coutdata; p=p-rchild; /非递归的后序遍历算法typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0;p=bt; do while (p!=NULL) /遍历左子树 stop.ptr = p; stop.tag