<span style="font-size:9pt;">实验原理：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　二叉树是最重要的一类树型结构，而二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，</span><span style="font-family:Tahoma;font-size:9pt;">C</span><span style="font-size:9pt;">语言用</span><span style="font-family:Tahoma;font-size:9pt;">NULL</span><span style="font-size:9pt;">表示，画图时用</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">表示。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　结点数据的数据类型应该根据实际应用进行选择，在本次实验中，选用字符类型。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span> 

<span style="font-size:9pt;">　　输入创建原理：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　创建二叉树可以用递归方式进行，下面用伪代码来描述创建流程：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　１、结点</span><span style="font-family:Tahoma;font-size:9pt;">* </span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">(){</span> 

<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-size:9pt;">定义结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 

<span style="font-size:9pt;">　　　　　　输入结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 

<span style="font-size:9pt;">　　　　　　如果　结点数据为空　则返回</span><span style="font-family:Tahoma;font-size:9pt;">NULL;//</span><span style="font-size:9pt;">规定输入字符</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">表示本结点不创建</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　　　　　创建结点</span><span style="font-family:Tahoma;font-size:9pt;">* node;</span> 

<span style="font-size:9pt;">　　　　　　赋值</span><span style="font-family:Tahoma;font-size:9pt;">node</span><span style="font-size:9pt;">的数据为刚刚输入的结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 

<span style="font-size:9pt;">　　　　　　</span><span style="font-family:Tahoma;font-size:9pt;">node.</span><span style="font-size:9pt;">左孩子</span><span style="font-family:Tahoma;font-size:9pt;">=</span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">();</span> 

<span style="font-size:9pt;">　　　　　　</span><span style="font-family:Tahoma;font-size:9pt;">node.</span><span style="font-size:9pt;">右孩子</span><span style="font-family:Tahoma;font-size:9pt;">=</span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">();</span> 

<span style="font-size:9pt;">　　　　　　返回</span><span style="font-family:Tahoma;font-size:9pt;"> node;</span> 

<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }</span> 

<span style="font-size:9pt;">　　２、在需要创建整棵二叉树的地方写上：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　　　　　　二叉树根结点　＝　创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">()</span><span style="font-size:9pt;">；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-family:Tahoma;font-size:9pt;">&nbsp; </span><span style="font-size:9pt;">　</span><span style="font-family:Tahoma;font-size:9pt;"> </span><span style="font-size:9pt;">遍历原理：要自己描述先序遍历、中序遍历原理。</span> 

<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span> 

<span style="font-size:9pt;">实验步骤：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　１、定义二叉链表结点类型；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　２、实现二叉链表创建方法；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　３、实现二叉链表的先序、中序遍历方法；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">　　４、实现主函数</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;"><span style="font-family:Tahoma;font-size:9pt;">&nbsp;

<span style="font-size:9pt;">每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">占位，如图的一棵二叉树。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">如果读到一行的第一个字符就是</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">，表示没有更多输入了，程序退出。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">测试时，每棵树不会超过</span><span style="font-family:Tahoma;font-size:9pt;">20</span><span style="font-size:9pt;">个结点。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-family:Tahoma;font-size:9pt;"></span>

<span style="font-size:9pt;">输入是：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-family:Tahoma;font-size:9pt;">AB^DE^^^C^^</span> 

<span style="font-family:Tahoma;font-size:9pt;">^</span> 

 

&nbsp;<span style="font-family:Tahoma;font-size:9pt;"><span style="font-family:Tahoma;font-size:9pt;">&nbsp;<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span></span></span></span></span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span style="font-size:9pt;">对于每个二叉树，分别进行先序遍历、中序遍历，每种遍历结果输出一行。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 

<span></span>