二叉树遍历 数据结构课程设计.doc
《二叉树遍历 数据结构课程设计.doc》由会员分享,可在线阅读,更多相关《二叉树遍历 数据结构课程设计.doc(23页珍藏版)》请在沃文网上搜索。
1、目 录摘要I第一章 问题定义1第二章 设计思路2第三章 数据结构定义3第四章 系统功能模块设计4第五章 运行与调试6总 结10附 录I1程序清单I2参考资料X摘要 本课设主要实现对二叉树进行的三种次序遍历,输出三种遍历次序的遍历序列。 先序遍历对二叉树进行根左右次序遍历,中序遍历对二叉树进行左根右次序遍历,后续遍历对二叉树进行左右根遍历次序。 采用二叉链表实现各种遍历操作。 关键字: 二叉树 二叉链表 遍历 I第一章 问题定义1.1 课题:建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法)以及中序线索化。1.2意义:通过以前的学习以及查看相关资料,按照题目要求编写程序,进一步加强
2、对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中去,在整个程序中,主要应用的是链表,但也运用了栈。通过两种方法解决现有问题。1.3要求:要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数; 实现二叉树的中序线索化。第二章 设计思路2.1中序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:(1)遍历左子树;(2)访问根结点;(3)遍历右子树。2.1先序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:(1) 访问根结点;(2) 遍历
3、左子树;(3) 遍历右子树。2.2后序遍历得递归算法定义:若二叉树非空,则依次执行如下操作:(1)遍历左子树;(2)遍历右子树;(3)访问根结点。第三章 数据结构定义二叉树定义:二叉树是另一种树形结构,(1)每个节点最多有两颗子树 。(2)子树有左右之分创建二叉树链表的结点存储结构及数据的输入函数。因为每个结点所存储的数据类型为字符串,却无法使用字符串和String等数据类型,所以使用单链表作为结点所存储的数据类型。以#表示空结点,利用先序遍历创建链表。 3.1用单链表s记录输入的数据。 3.2利用非递归调用分别生成根节点的左子树和右子树。3.3返回菜单重新选择。基本程序如下:void Cre
4、atBiTree_q(BiTree &T)/ if(ch=#) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T) exit(0); T-data=ch; T-LTag=Link; T-RTag=Link; CreatBiTree_q(T-lchild); CreatBiTree_q(T-rchild);第四章 系统功能模块设计4.1调用生成二叉树的函数,从键盘输入二叉树的各个结点4.2分别调用先序遍历、中序遍历、后序遍历二叉树的函数,输出所有结点显示的菜单为: * 请选择遍历算法 1.按先序输入二叉树序列以#表示空节点 2.先序遍历二叉
5、树递非归算法 3.中序遍历二叉树非递归算法 4.后序遍历二叉树非递归算法 5.层次遍历二叉树非递归算法 6.中序线索遍历二叉树算法 0.按0退出endl 请输入序号(0,1,2,3,4,5,6): A B C D E F G 输入的二叉树是:ABC#DE#F#G#(#代表空结点)输出的遍历应该是:先序遍历:A B C D E F G 中序遍历:C B E F D G A 后序遍历:C B G E F D A 层序遍历:A B C D E F G 中序线索化遍历:C B E F D G A第五章 运行与调试5.1菜单界面:5.2创建界面:5.3先序非遍历二叉树:5.4中序非遍历二叉树:5.5后序
6、非遍历二叉树:5.6层次遍历二叉树:5.7中序线索化,中序遍历:总 结实验开始时定义结构时,比细心,总会有或多或少的问题出现,如数据域和指针域定义的类型不一样,在实验过程中总有这样或那样的问题,在本次实验中,二叉树的先序,中序,后序遍历都是采用非递归调用,用起来稍微复杂,这使我更进一步学习和理解了树的遍历,更灵活地运用了指针与数组10附 录1程序清单#include #include #include #include #define Link 0#define Thread 1int right=0;typedef char TElemType; typedef struct BiTNode
7、 TElemType data; struct BiTNode *lchild,*rchild; int LTag, RTag,flag; BiTNode,*BiTree; BiTree pre; void CreatBiTree_q(BiTree &T) TElemType ch; scanf(%c,&ch); if(ch=#) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T) exit(0); T-data=ch; T-LTag=Link; T-RTag=Link; CreatBiTree_q(T-lchild); CreatBiT
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉树遍历 数据结构课程设计 二叉 遍历 数据结构 课程设计