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

吉林工程技术师范学院《数据结构》课程设计报告书设计题目: 二叉树遍历专业: 软件班级: 2班学生姓名: 隋晓宇学号: 18 指导教师: 王锐高岚 2012 年12月信息工程学院目录摘要................................................................................. I 第一章问题定义.......................................................... 1 第二章设计思路.......................................................... 2 第三章数据结构定义.................................................. 3 第四章系统功能模块设计.......................................... 4 第五章运行与调试...................................................... 6 总结........................................................................... 10 附录............................................................................. I 1 程序清单................................................................ I 2 参考资料.............................................................. X I 摘要本课设主要实现对二叉树进行的三种次序遍历,输出三种遍历次序的遍历序列。先序遍历对二叉树进行根左右次序遍历,中序遍历对二叉树进行左根右次序遍历,后续遍历对二叉树进行左右根遍历次序。采用二叉链表实现各种遍历操作。关键字: 二叉树二叉链表遍历 1 第一章问题定义 课题: 建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法)以及中序线索化。 意义: 通过以前的学****以及查看相关资料,按照题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中去,在整个程序中,主要应用的是链表,但也运用了栈。通过两种方法解决现有问题。 要求: 要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数;实现二叉树的中序线索化。 2 第二章设计思路 中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1) 遍历左子树; (2) 访问根结点; (3) 遍历右子树。 2 .1 .先序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1) 访问根结点; (2) 遍历左子树; (3) 遍历右子树。 后序遍历得递归算法定义: 若二叉树非空,则依次执行如下操作: (1) 遍历左子树; (2) 遍历右子树; (3) 访问根结点。 3 第三章数据结构定义二叉树定义:二叉树是另一种树形结构,(1)每个节点最多有两颗子树。(2) 子树有左右之分创建二叉树链表的结点存储结构及数据的输入函数。因为每个结点所存储的数据类型为字符串,却无法使用字符串和 String 等数据类型,所以使用单链表作为结点所存储的数据类型。以#表示空结点,利用先序遍历创建链表。 用单链表 s记录输入的数据。 利用非递归调用分别生成根节点的左子树和右子树。 返回菜单重新选择。基本程序如下: void CreatBiTree_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 第四章系统功能模块设计 调用生成二叉树的函数,从键盘输入二叉树的各个结点 分别调用先序遍历、中序遍历、后序遍历二叉树的函数,输出所有结点显示的菜单为: **********************************************