实验原理：

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

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

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

　　输入创建原理：

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

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

                    定义结点数据;

　　　　　　输入结点数据;

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

　　　　　　创建结点* node;

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

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

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

　　　　　　返回 node;

             }

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

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

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

实验步骤：

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

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

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

　　４、实现主函数

思考题：

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

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

程欣宇2014年4月

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

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

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

输入是：

AB^DE^^^C^^

^

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