实验五——二叉树

按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件验证该头文件中各个操作。

二叉树二叉链表存储表示如下：
typedef struct BiTNode {
     TElemType  data ;
     struct BiTNode  *lchild , *rchild ;
}BiTNode,*BiTree ;
基本操作如下：
①void InitBiTree(BiTree &T )  
//初始化二叉树T 
②void CreateBiTree(BiTree &T) 
//按先序遍历序列建立二叉链表T     
③bool BiTreeEmpty (BiTree T);         
//检查二叉树T是否为空，空返回1，否则返回0 
④int BiTreeDepth(BiTree T);
//求二叉树T的深度并返回该值                       
⑤void PreOrderTraverse (BiTree T);    
//先序遍历二叉树T
⑥void InOrderTraverse (BiTree T);
//中序遍历二叉树T
⑦void PostOrderTraverse (BiTree T);  
//后序遍历二叉树T
⑧void DestroyBiTree(BiTree &T)       
//销毁二叉树T   

//二叉树结构
typedef struct BiTNode {
     TElemType  data ;
     struct BiTNode  *lchild , *rchild ;
}BiTNode,*BiTree ;
class Tree {
public:
    BiTree node;
    Status InitBiTree(BiTree &T);
    Status CreateBiTree(BiTree &T, char *str);
    bool BiTreeEmpty(BiTree T);
    int BiTreeDepth(BiTree T);
    Status PreOrderTraverse(BiTree T);
    Status InOrderTraverse(BiTree T);
    Status PostOrderTraverse(BiTree T);
    Status DestroyBiTree(BiTree &T);
};
//初始化二叉树T
Status Tree::InitBiTree(BiTree &T) {
    T = NULL;
    return OK;
}
//按先序遍历序列建立二叉链表T
static int i = 0;
Status Tree::CreateBiTree(BiTree &T, char *str) {
    TElemType c;

    c = *(str + i++);
    //printf("%s\n", str);
    //printf("%d%c\n", i,c);
    //i=++i;
    if (c == '#') {
        T = NULL;
    } else {
        //BiTNode *T=new BiTNode;
        T=new BiTNode;
        //T = (BiTree) malloc(sizeof(BiTNode));
        if (!T) {
            return ERROR;
        }

        T->data = c;
        CreateBiTree(T->lchild, str);
        CreateBiTree(T->rchild, str);
    }
    if (i == strlen(str))
        i = 0;
}
//检查二叉树T是否为空，空返回1，否则返回0
bool Tree::BiTreeEmpty(BiTree T) {
    if (!T) {
        return false;
    } else {
        return true;
    }
}
//求二叉树T的深度并返回该值
int Tree::BiTreeDepth(BiTree T) {
    int i, j;
    if (!T) {
        return ERROR;
    }
    if (T->lchild) {
        i = BiTreeDepth(T->lchild);
    } else {
        i = 0;
    }
    if (T->rchild) {
        j = BiTreeDepth(T->rchild);
    } else {
        j = 0;
    }
    return i > j ? i + 1 : j + 1;
}
//先序遍历二叉树T
Status Tree::PreOrderTraverse(BiTree T) {
    if (!T) {
        return OK;
    }
    visit(T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
    return OK;
}
//中序遍历二叉树T
Status Tree::InOrderTraverse(BiTree T) {
    if (!T) {
        return OK;
    }

    InOrderTraverse(T->lchild);
    visit(T->data);
    InOrderTraverse(T->rchild);
    return OK;
}
//后序遍历二叉树T
Status Tree::PostOrderTraverse(BiTree T) {
    if (!T) {
        return OK;
    }

    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    visit(T->data);
    return OK;
}
//销毁二叉树T
Status Tree::DestroyBiTree(BiTree &T) {
    if (T) {
        if (T->lchild) {
            DestroyBiTree(T->lchild);
        }
        if (T->rchild) {
            DestroyBiTree(T->rchild);
        }
        free(T);
        //T=NULL;
        return OK;
    }
}