#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0

typedef char TElemType;
typedef int  Status;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

Status CreateBiTree(BiTree *T) ///BiTNode T
{
    char ch;
    ch=getchar();
    if(ch=='#')(*T)=NULL;///#代表空指針
    else
    {
        (*T)=(BiTree)malloc(sizeof(BiTNode));
        (*T)->data=ch;///生成根結(jié)點
        CreateBiTree(&(*T)->lchild);///構(gòu)造左子樹
        CreateBiTree(&(*T)->rchild);///構(gòu)造右子樹
    }
    return 1;
}

///先序遍歷輸出
void PreOrder(BiTree T)
{
    if(T)
    {
        printf("%2c",T->data);///T->data==(*T).data
        PreOrder(T->lchild);///先序遍歷左子樹
        PreOrder(T->rchild);///先序遍歷右子樹
    }
}

///中序遍歷輸出
void InOrder(BiTree T)
{
    if(T)
    {
        InOrder(T->rchild);///中序遍歷右子樹
        printf("%2c",T->data);
        InOrder(T->lchild);///中序遍歷左子樹

    }
}
///后序遍歷輸出
void Postorder(BiTree T)
{
    if(T)
    {
        Postorder(T->lchild);///后序遍歷左子樹
        Postorder(T->rchild);///后序遍歷右子樹
        printf("%2c",T->data);///訪問根結(jié)點
    }
}
///層次遍歷二叉樹T，從第一層開始，每層從左到右
void LevleOrder(BiTree T)
{
    BiTree Queue[MAX],b;
    ///用一維數(shù)組表示隊列，front和rear分別表示隊首和隊尾指針
    int front,rear;
    front=rear=0;
    if(T) ///若樹非空
    {
        Queue[rear++]=T;///根結(jié)點入隊列
        while(front!=rear) ///當(dāng)隊列非空
        {
            b=Queue[front++];///隊首元素出隊列，并訪問這個結(jié)點
            printf("%2c",b->data);
            if(b->lchild!=NULL)
            {
                Queue[rear++]=b->lchild;
                ///左子樹非空，則入隊列

            }
            if(b->rchild!=NULL)
            {
                Queue[rear++]=b->rchild;
                ///右子樹非空，則入隊列
            }
        }
    }
}


///求二叉樹的深度
int depth(BiTree T){
    int dep1,dep2;
    if(T==NULL)  return 0;
    else
    {
        dep1=depth(T->lchild);
        dep2=depth(T->rchild);
        return dep1>dep2?dep1+1:dep2+1;
    }
}


int main()
{
    BiTree T=NULL;///（開始定義的是*T）此時T為地址
    printf("\n建立一棵二叉樹T:\n");
    CreateBiTree(&T);///建立一棵二叉樹
    printf("\nThe preorder(先序序列為)is:\n");
    PreOrder(T);
    printf("\nThe inorder(中序序列為)is:\n");
    InOrder(T);
    printf("\nThe Postorder(后序序列為)is:\n");
    Postorder(T);
    printf("\nThe levle order(層次序列為)is:\n");
    LevleOrder(T);
    printf("\nThe depth(深度)is:%d\n",depth(T));
    getchar();
    return 0;
}