/*作者：***
时间2023.5.6.  19:36
功能：实现二叉树的创建、前中后层序遍历、测量深度*/
#include<stdio.h>
#include<stdlib.h>
typedef struct Binnode
{
    char info;
    struct Binnode *left;
    struct Binnode *right;
}*Bintree;
typedef struct Queue
{
    Bintree node;
    struct Queue *next;
}*Qu;//队列
typedef struct Quhead
{
    Qu head;
    Qu tail;
}*Quhd;//队头
Bintree CreateBintree();//根据前序遍历的结果创建二叉树
void PreOrder(Bintree Bt);//前序遍历
void InOrder(Bintree Bt);//中序遍历
void PostOrder(Bintree Bt);//后序遍历
void LevelOrder(Bintree Bt);//层序遍历
void Level(struct Quhead *qhead,Bintree Bt);

void EnQueue(Quhd qu,Bintree node);//入队
Bintree DeQueue(Quhd qu);//出队

int BintreeDepth(Bintree Bt);//测量深度
void Depth(Bintree Bt,int h,int *depth);//另一种测量深度的方法
void Destroy(Bintree Bt);//释放函数

int main()
{
    Bintree tree;//这是二叉树
    int or;//判断是否继续进行
    int h = 1;//用来存放当前所在层次
    int depth = 0;//用来存放当前已知的最大层次
    int result = -1;
    do
    {
        printf("Please input your bin tree in preorder:\n");
        tree = CreateBintree();
        printf("Preorder result:");
        PreOrder(tree);
        printf("\n");

        printf("Inorder result:");
        InOrder(tree);
        printf("\n");

        printf("Postorder result:");
        PostOrder(tree);
        printf("\n");

        printf("Levelorder result:");
        LevelOrder(tree);
        printf("\n");
        result = BintreeDepth(tree);
        printf("The depth of the tree is %d\n",result);
        Depth(tree,h,&depth);
        printf("In another manner ,the depth is %d\n",depth);
        printf("Do you want to go on?\n");
        scanf("%d",&or);
        Destroy(tree);
        if(or)
        {
            getchar();
        }
    }while(or>0);

    return 0;
}
Bintree CreateBintree()
{
    char c;
    Bintree t = NULL;
    c = getchar();
    if(c == ' ')
        return NULL;
    else
    {
        t = (Bintree)malloc(sizeof(struct Binnode));
        if(t == NULL)
        {
            printf("ERROR!");
            exit(0);
        }
        t->info = c;
        t->left = CreateBintree();
        t->right = CreateBintree();
    }
    return t;
}
void PreOrder(Bintree Bt)
{
    if(!Bt)
    {
        return;
    }
    else
    {
        printf("%c",Bt->info);
        PreOrder(Bt->left);
        PreOrder(Bt->right);
    }
}
void InOrder(Bintree Bt)
{
    if(!Bt)
    {
        return;
    }
    else
    {
        InOrder(Bt->left);
        printf("%c",Bt->info);
        InOrder(Bt->right);
    }
}
void PostOrder(Bintree Bt)
{
    if(!Bt)
    {
        return;
    }
    else
    {
        PostOrder(Bt->left);
        PostOrder(Bt->right);
        printf("%c",Bt->info);
    }
}
int BintreeDepth(Bintree Bt)//测量深度
{
    int hL,hR;
    if(!Bt)
        return 0;
    else
    {
        hL = BintreeDepth(Bt->left);
        hR = BintreeDepth(Bt->right);
    }
    if(hL>hR)
    {
        return hL+1;
    }
    else
    {
        return hR+1;
    }
}
void Depth(Bintree Bt,int h,int *depth)
{
    if(!Bt)
    {
        return;
    }
    else
    {
        if(h>*depth)
            *depth = h;
        Depth(Bt->left,h+1,depth);
        Depth(Bt->right,h+1,depth);
    }
}
void LevelOrder(Bintree Bt)//层序遍历
{
    Quhd qhead = (Quhd)malloc(sizeof(struct Quhead));
    if(qhead == NULL)
    {
        printf("ERROR!");
        exit(0);
    }
    qhead->head = NULL;
    qhead->tail = NULL;
    Level(qhead,Bt);
    free(qhead);
}
void Level(Quhd qhead,Bintree Bt)
{
    Bintree t;
    EnQueue(qhead,Bt);
    while(qhead->head != NULL||qhead->tail != NULL)
    {
        t = DeQueue(qhead);
        printf("%c",t->info);
        if(t->left)
            EnQueue(qhead,t->left);
        if(t->right)
            EnQueue(qhead,t->right);
    }
}
void Destroy(Bintree Bt)
{
    if(Bt->left)
    {
        Destroy(Bt->left);
    }
    else if(Bt->right)
    {
        Destroy(Bt->right);
    }
    free(Bt);
    return;
}
void EnQueue(Quhd qu,Bintree node)//入队
{
    Qu t = NULL;
    t = (Qu)malloc(sizeof(struct Queue));
    if(t == NULL)
    {
        printf("ERROR!");
        exit(0);
    }
    if(qu->head == NULL&&qu->tail == NULL)
    {
        t->node = node;
        qu->head = qu->tail = t;
        t->next = NULL;
    }
    else
    {
        t->node = node;
        t->next = qu->tail->next;
        qu->tail->next = t;
        qu->tail = t;
    }

}
Bintree DeQueue(Quhd qu)//出队
{
    if(qu->head == NULL&&qu->tail == NULL)
        return NULL;
    Qu t = NULL;
    Bintree k = NULL;
    if(qu->head == qu->tail)
    {
        t = qu->head;
        k = t->node;
        free(t);
        qu->head = qu->tail = NULL;
        return k;
    }
    else
    {
        t = qu->head;
        qu->head = qu->head->next;
        k = t->node;
        free(t);
        return k;
    }


}