说明

实验原理：

二叉树是最重要的一类树型结构。二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。

其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，C语言用NULL表示，画图时用^表示。

结点数据的数据类型应该根据实际应用选择，在本次实验中，为了方便输入和输出，我们选用字符类型。

输入创建原理：

二叉树虽然可以很复杂，但是创建二叉树可以用递归方式进行，代码只需要几行，下面我们用伪代码来描述创建流程：

１、结点* 创建结点函数(){

定义结点数据;

输入结点数据;

如果　结点数据为空　则返回NULL;//这里比较重要，我们规定输入字符^表示本结点不创建

创建结点* node;

赋值node的数据为刚刚输入的结点数据;

node.左孩子=创建结点函数();

node.右孩子=创建结点函数();

返回 node;

}

２、在需要创建整课二叉树的地方写上：

二叉树根结点　＝　创建结点函数()；

遍历原理：先根遍历、后根遍历、中根遍历原理，请自行补充，

实验步骤：

１、定义二叉链表结点类型；

２、实现二叉链表创建方法；

３、实现二叉链表的三种遍历方法；

４、实现主函数

思考题：

1：为什么很多数据结构会有遍历的需求？

2：如何干净地释放整棵二叉树动态申请的所有结点？

输入格式

每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符^占位，如图的一棵二叉树。

如果读到一行的第一个字符就是^，表示没有更多输入了，程序退出。

测试时，每棵树不会超过20个结点。

输入是：

AB^DE^^^C^^

^

输出格式

对于每个二叉树，分别进行先根遍历、中根遍历、后根遍历，每种遍历结果输出一行。

样例

输入数据 1

DL^^R^^
AB^DE^^^C^^
^

输出数据 1

DLR
LDR
LRD
ABDEC
BEDAC
EDBCA

提示

1、主函数可以采用以下流程

int main(){

定义结点指针;

do{

结点指针=创建结点函数();

if (结点指针非空){

先根遍历;换行

中根遍历;换行

后根遍历;换行

}

}while(结点指针非空);

return 0;

}

2、

如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：

char ch; do{ scanf("%c",&ch); }while(ch<=32);//确保读到一个非空白非换行的字符