实验八：二叉树的遍历（2学时）

树和二叉树是应用极为广泛的数据结构，也是这门课程的重点。本次实验将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。

（一）问题描述

很多涉及二叉树操作的算法都是以遍历操作为基础的。试写一程序，实现对二叉树的遍历。

1．分别用三种递归方法：先序、中序和后序。

2．利用队列按层次遍历。注意正确使用队列中的定义和函数。

 

其实，二叉树也可以实现非递归的遍历，有兴趣的可以试着写写，书上有中序非递归遍历算法。

（二）基本要求

1．用二叉链表的形式存储一棵二叉树，见书上Create（）函数。

注意输入先序前必须补齐空的结点，可用 # 号补齐。

 

2．

分别用三种递归方法：先序、中序和后序输出结果。

利用队列按层次遍历。注意正确使用队列中的定义和函数

（三）测试数据

请至少准备3棵不同形态二叉树进行测试。

可自拟，也可采用书上的。

 

（四）实现提示

二叉树的建树过程参照131页算法6.4，下图的二叉树，输入的先序序列应为

abd##e#g##cf###，而不是abdegcf。