11817: 数据结构/二叉树/创建与遍历（软件1、2）
Description
实验原理：
二叉树是最重要的一类树型结构，而二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。
其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，C语言用NULL表示，画图时用^表示。
结点数据的数据类型应该根据实际应用进行选择，在本次实验中，选用字符类型。
输入创建原理：
创建二叉树可以用递归方式进行，下面用伪代码来描述创建流程：
１、结点* 创建结点函数(){
定义结点数据;
输入结点数据;
如果 结点数据为空 则返回NULL;//规定输入字符^表示本结点不创建
创建结点* node;
赋值node的数据为刚刚输入的结点数据;
node.左孩子=创建结点函数();
node.右孩子=创建结点函数();
返回 node;
}
２、在需要创建整棵二叉树的地方写上：
二叉树根结点 ＝ 创建结点函数()；
遍历原理：要自己描述先序遍历、中序遍历原理。
实验步骤：
１、定义二叉链表结点类型；
２、实现二叉链表创建方法；
３、实现二叉链表的先序、中序遍历方法；
４、实现主函数
Input
每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符^占位，如图的一棵二叉树。
如果读到一行的第一个字符就是^，表示没有更多输入了，程序退出。
测试时，每棵树不会超过20个结点。
输入是：
AB^DE^^^C^^
^
Output
对于每个二叉树，分别进行先序遍历、中序遍历，每种遍历结果输出一行。
Sample Input Copy
DL^^R^^
AB^DE^^^C^^
^
Sample Output Copy
DLR
LDR
ABDEC
BEDAC
HINT
1、主函数可以采用以下流程
int main(){
定义结点指针;
do{
结点指针=创建结点函数();
if (结点指针非空){
先序遍历;换行
中序遍历;换行
}
}while(结点指针非空);
return 0;
}
2、
如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：
char ch;
do{
scanf("%c",&ch);
}while(ch<=32);//确保读到一个非空白非换行的字符