树、二叉树(二)

限于篇幅过长上一篇我们只谈了树、二叉树(一)比较基础的认识，下面我们深入的学习树与二叉树。

顺序存储结构

使用一组地址(一维数组)连续的存储单元来存储数据元素

    //-------二叉树的顺序存储表示---------
    #define MAXTSIZE 100  //二叉树的最大结点数
    typedef TElemType SqBiTree[MAXTSIZE];
    SqBiTree bt;

完全二叉树：只需要从根起按层序存储，依次自上而下、自左至右存储结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。

一般二叉树：一般二叉树同样要遵循完全二叉树的规则，将结点进行相对照，存储在一维数组的相对应分量中。

顺序存储的优点与缺点

1. 对于完全二叉树来说，顺序存储结构既简单又节约存储空间。
2. 一般的二叉树采取顺序存储结构时，虽然简单，但容易造成存储空间的浪费。
3. 在顺序存储的二叉树做插入和删除结点时，要大量移动结点。

链式存储结构

对照上面顺序存储结构的不足，我们引入了链式存储，二叉树的结点至少有三个域：数据域、左、右指针域。有时候我们还要知道它的双亲，所以还要加上一个指向双亲结点的指针域。

//----二叉树的二叉链表存储表示---
typedef struct BiTNode{
TElemType data；//结点数据域
struct BiTNode *lchild，*rchild；//左右孩子指针
}BiTNode，*BiTree;

遍历二叉树

遍历二叉树是沿着某个指定路径有规律的进行访问树的每一个结点，保证每个结点均能被访问一次，并且只能被访问一次。

遍历的实质是通过遍历结果将非线性结构的树中结点排成一个线性序列。

通过上一篇树、二叉树(一)
我们得知二叉树有根结点（D）、左子树（L）和右子树（R）三部分组成。
根据高中数学知识得知一共有DLR、LDR、LRD、DRL、RDL、RLD六种方式遍历。但若限定先左后右的原则则只有DLR、LDR、LRD三种情况，分别称为先（根）序遍历、中（根）序遍历、后（根）序遍历。

先序遍历

（1）访问根节点；

（2）先序遍历左子树；

（3）先序遍历右子数。

Status PreOrderTraverse(BiTree T)
{
 if(T==NULL)return OK;//空二叉树
 else{
 cout<<T->data;//访问根结点
 Pre