//
// Created by 方朋 on 2017/1/4.
//

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;		    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char TElemType;
TElemType Nil = ' ';        // 字符型以空格为空

typedef struct BiTNode      // 结点结构
{
    TElemType data;                 // 结点数据
    struct BiTNode *lchild, *rchild;    // 左右孩子指针
}BiTNode, *BiTree;

/* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
    *T=NULL;
    return OK;
}

/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
/* 大话数据结构树: C6.9 小结 */
void CreateBiTree(BiTree *T)
{
    TElemType ch;
    scanf ("%c", &ch);
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc (sizeof (struct BiTNode));
        if(!*T)
            exit (2);
        (*T)->data = ch;                // 生成根结点
        CreateBiTree (&(*T)->lchild);   // 构造左子树
        CreateBiTree (&(*T)->rchild);   // 构造右子树
    }
}

int BiTreeEmpty (BiTree T)
{
    return T ? 0 : 1;
}

int BiTreeDepth(BiTree T)
{
    int i, j;
    if (!T) return 0;

    i = T->lchild ? BiTreeEmpty (T->lchild) : 0;
    j = T->rchild ? BiTreeEmpty (T->rchild) : 0;
    return i > j ? i+1 : j+1;
}

TElemType Root(BiTree T)
{
    return T ? T->data : Nil;
}

void PreOrderTraverse(BiTree T)
{
    if (T == NULL) return;
    printf ("%c", T->data);
    PreOrderTraverse (T->lchild);
    PreOrderTraverse (T->rchild);
}

void InOrderTraverse(BiTree T)
{
    if (T == NULL) return;
    PreOrderTraverse (T->lchild);
    printf ("%c", T->data);
    PreOrderTraverse (T->rchild);
}

void PostOrderTraverse(BiTree T)
{
    if (T == NULL) return;
    PreOrderTraverse (T->lchild);
    PreOrderTraverse (T->rchild);
    printf ("%c", T->data);
}

/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T)
{
    if (*T)
    {
        if ((*T)->lchild)       // 如有左孩子则递归销毁左孩子
            DestroyBiTree (&(*T)->lchild);

        if ((*T)->rchild)       // 如有右孩子则递归销毁右孩子
            DestroyBiTree (&(*T)->lchild);

        free (*T);      // 释放根结点
        *T = NULL;      // 空指针赋null
    }

}

#define ClearBiTree DestroyBiTree


int main()
{
    int i;
    BiTree T;
    TElemType e1;

    InitBiTree(&T);

    CreateBiTree(&T);
    printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));

    e1=Root(T);
    printf("二叉树的根为: %c\n",e1);

    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);

    ClearBiTree(&T);
    printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    i=Root(T);
    if(!i)
        printf("树空，无根\n");

}