#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;///生成根结点
        CreateBiTree(&(*T)->lchild);///构造左子树
        CreateBiTree(&(*T)->rchild);///构造右子树
    }
    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);///访问根结点
    }
}
///层次遍历二叉树T，从第一层开始，每层从左到右
void LevleOrder(BiTree T)
{
    BiTree Queue[MAX],b;
    ///用一维数组表示队列，front和rear分别表示队首和队尾指针
    int front,rear;
    front=rear=0;
    if(T) ///若树非空
    {
        Queue[rear++]=T;///根结点入队列
        while(front!=rear) ///当队列非空
        {
            b=Queue[front++];///队首元素出队列，并访问这个结点
            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;
}