数据结构课程设计

吉林工程技术师范学院。

设计题目：二叉树遍历。

专业：软件。

班级： 2班。

学生姓名：隋晓宇

学号18指导教师：王锐高岚

2024年12月。

信息工程学院。

目录。摘要 i

第一章问题定义 1

第二章设计思路 2

第三章数据结构定义 3

第四章系统功能模块设计 4

第五章运行与调试 6

总结 10附录 i

1程序清单 i

2参考资料 x

本课设主要实现对二叉树进行的三种次序遍历，输出三种遍历次序的遍历序列。

先序遍历对二叉树进行根左右次序遍历，中序遍历对二叉树进行左根右次序遍历，后续遍历对二叉树进行左右根遍历次序。

采用二叉链表实现各种遍历操作。

关键字：二叉树二叉链表遍历

1.1 课题：

建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法）以及中序线索化。

1.2意义：

通过以前的学习以及查看相关资料，按照题目要求编写程序，进一步加强对编程的训练，使得自己掌握一些将书本知识转化为实际应用当中去，在整个程序中，主要应用的是链表，但也运用了栈。通过两种方法解决现有问题。

1.3要求：

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；实现二叉树的中序线索化。

2.1中序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

1)遍历左子树；

2)访问根结点；

3)遍历右子树。

2.1．先序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

1) 访问根结点；

2) 遍历左子树；

3) 遍历右子树。

2.2后序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

1)遍历左子树；

2)遍历右子树；

3)访问根结点。

二叉树定义：二叉树是另一种树形结构，（1）每个节点最多有两颗子树。(2)子树有左右之分。

创建二叉树链表的结点存储结构及数据的输入函数。

因为每个结点所存储的数据类型为字符串，却无法使用字符串和string等数据类型，所以使用单链表作为结点所存储的数据类型。以#表示空结点，利用先序遍历创建链表。

3.1用单链表s记录输入的数据。

3.2利用非递归调用分别生成根节点的左子树和右子树。

3.3返回菜单重新选择。

基本程序如下：

void creatbitree_q(bitree &t)/

if(ch=='#

t=null;else

4.1调用生成二叉树的函数，从键盘输入二叉树的各个结点。

4.2分别调用先序遍历、中序遍历、后序遍历二叉树的函数，输出所有结点。

显示的菜单为：

请选择遍历算法。

1.按先序输入二叉树序列以#表示空节点。

2.先序遍历二叉树递非归算法

3.中序遍历二叉树非递归算法。

4.后序遍历二叉树非递归算法。

5.层次遍历二叉树非递归算法。

6.中序线索遍历二叉树算法。

0.按0退出"< 请输入序号（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后序非遍历二叉树：

5.6层次遍历二叉树：

5.7中序线索化，中序遍历：

实验开始时定义结构时，比细心，总会有或多或少的问题出现，如数据域和指针域定义的类型不一样，在实验过程中总有这样或那样的问题，在本次实验中，二叉树的先序，中序，后序遍历都是采用非递归调用，用起来稍微复杂，这使我更进一步学习和理解了树的遍历，更灵活地运用了指针与数组。

#include <>

#define link 0

#define thread 1

int right=0;

typedef char telemtype;

typedef struct bitnode

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);

creatbitree_q(t->rchild);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了