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

吉林工程技术师范学院
《数据结构》课程设计报告书
设计题目: 二叉树遍历
专业: 软件
班级: 2班
学生姓名: 隋晓宇
学号: 18
指导教师: 王锐高岚

2012年12月
信息工程学院
目录
摘要 I
第一章问题定义 1
第二章设计思路 2
第三章数据结构定义 3
第四章系统功能模块设计 4
第五章运行与调试 6
总结 10
附录 I
1程序清单 I
2参考资料 X
摘要
本课设主要实现对二叉树进行的三种次序遍历,输出三种遍历次序的遍历序列。
先序遍历对二叉树进行根左右次序遍历,中序遍历对二叉树进行左根右次序遍历,后续遍历对二叉树进行左右根遍历次序。
采用二叉链表实现各种遍历操作。

关键字: 二叉树二叉链表遍历
第一章问题定义
课题:
建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法)以及中序线索化。
:
通过以前的学****以及查看相关资料,按照题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中去,在整个程序中,主要应用的是链表,但也运用了栈。通过两种方法解决现有问题。
:
要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数; 实现二叉树的中序线索化。
第二章设计思路
:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
:
若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。
第三章数据结构定义
二叉树定义:二叉树是另一种树形结构,(1)每个节点最多有两颗子树。(2)子树有左右之分
创建二叉树链表的结点存储结构及数据的输入函数。
因为每个结点所存储的数据类型为字符串,却无法使用字符串和String等数据类型,所以使用单链表作为结点所存储的数据类型。以#表示空结点,利用先序遍历创建链表。
。
。
。
基本程序如下:
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);}}
第四章系统功能模块设计
,从键盘输入二叉树的各个结点
、中序遍历、后序遍历二叉树的函数,输出所有结点
显示的菜单为:
***********************************************
请选择遍历算法
#表示空节点





"<<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
第五章运行与调试
:
:
: