题目：二叉树操作验证
1.实验目的
(1)掌握二叉树的逻辑结构
(2)掌握二叉树的二叉链表存储结构；
(3)掌握基于二叉链表存储的二叉树的遍历操作的实现。
2.实验内容
(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；
(2) 前序（或中序、后序）遍历该二叉树。
3.实现提示
二叉链表的结点结构如图所示。
|
lchild |
data |
rchild |
图 二叉树的结点结构
二叉链表的结点用C++中的结构类型描述为：
template <class T>
struct BiNode
｛
T data；
BiNode<T> * lchild，*rchild；
｝；
设计实验用二叉链表类BiTree，类中包含遍历操作。
template <class T>
class BiTree
｛
public：
BiTree(BiNode<T> *root)；//有参构造函数,初始化一棵二叉树，
//其前序序列由键盘输入
~BiTree（）； //析构函数，释放二叉链表中各结点的存储空间
void PreOrder(BiNode<T> *root)；//前序遍历二叉树
void InOrder(BiNode<T> *root)；//中序遍历二叉树
void PostOrder(BiNode< T＞ *root)； //后序遍历二叉树
private：
BiNode<T＞ *root； //指向根结点的头指针
void Creat(BiNode<T> *root)； //有参构造函数调用
void Release(BiNode<T>*root)； //析构函数调用
｝；
设计构造函数，建立一棵二叉树的二叉链表存储。
将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如＃，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的一个遍历序列就能惟一确定一棵二叉树。假设扩展二叉树的前序遍历序列由键盘输人，root为指向根结点的指针，二叉链表的建立过程是：首先输人根结点，若输人的是一个＃字符，则表明该二叉树为空树，即root =NULL；否则输人的字符应该赋予root ->data，之后依次递归建
立它的左子树和右子树。建立二叉链表的递归算法如下：
二叉树的构造函数算法BiTree
template<class T>
BiTree :: BiTree (BiNode<T> *root)
{
root = creat( );
}
template <class T>
BiNode<T> * BiTree :: Creat( )
{
Cin>>ch;
if (ch = =’#’) return NULL; //建立一棵空树
else{
root = new BiNode<T>; //生成一个结点
root ->data = ch;
root ->lchild = Creat( ); //递归建立左子树
root ->rchile = Creat( ); //递归建立右子树
}
}