题目：线索二叉树
一、需求分析
1． 输入形式及输入值范围
按照先序建立二叉树的形式输入一串字符，空树以’&’作为标记。
输入值可以是任何的字符，但’&’除外，’&’被作为结束输入的标记。
2. 输出标准
按照中序遍历输出所建好的二叉树。
3. 若二叉树建立成功，则该程序最后输出一个字符串，并可以查找任意字符的前驱和后
继，将它们输出。
4. 测试数据
输入：ab&&c&&
输出：bac
请输入要查找的结点：a
a 的前驱为：b，后继为：c
二、概要设计
1）设定二叉树的抽象数据类型定义：
ADT BinaryTree{
数据结构 D：D 是具有相同特性的数据元素的组合。
数据关系 R：
若 D=Ф,则 R=Ф，称 BinatryTree 为空二叉树；
若 D≠Ф,则 R={H}，H 是如下二元关系：
（1） 在 D 中存在惟一的称谓根的数据元素 root，它在关系 H 下无前驱；
（2） 若 D-{root}≠Ф，则存在 D-{root}={D1，Dr}，D1∩Dr=Ф；
（3） 若 D1≠Ф，在 D1 中存在惟一的元素 X1，<root,X1>∈H,且存在
D1 上 的 关 系 H1∈H; 若 Dr≠Ф ， 则 Dr 中 存 在 惟 一 的 元 素
Xr ， <root,Xr>∈H ， 且 存 在 Dr 上 的 关 系 H1∈H ；
H={<root，X1}，<root，Xr>};
（4） (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,
{Hr})是一颗符合本定义的二叉树，称为根的右子树。
基本操作：
InitBiTree(&T);
操作结果：构造空二叉树 T。
DestroyBiTree(&T);
初始条件：二叉树 T 存在。
操作结果：销毁二叉树 T。
CreatBiTree(&T,de#nition);
初始条件：de#nition 给出二叉树 T 的定义。
操作结果：按 de#nition 构造二叉树 T。
ClearBiTree(&T);
初始条件：二叉树 T 存在。
操作结果：将二叉树 T 清为空树。
PreOrdTraverse(T,Visit());
