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

//二叉树结点定义
typedef struct BT
{
    char data;
    struct BT *lchild;
    struct BT *rchild;
}BT;

//建立二叉树(前序创建)
BT *createtree()
{
    BT *bt;
    char x;
    scanf("%c",&x);
    if (x == '0')
        bt = NULL;
    else
    {
        bt = (BT *)malloc(sizeof(BT));
        bt->data = x;
        bt->lchild = createtree();
        bt->rchild = createtree();
    }
    return (bt);
}

//前序递归遍历
void  Preorder(BT *bt)
{
    if (bt != NULL)
    {
        printf("%c ",bt->data);
        Preorder(bt->lchild);
        Preorder(bt->rchild);
    }
}

int count = 0;
//统计二叉树叶子结点数
void leafnum(BT *bt)   //开始时,bt指向根结点,count(初值为0)作为全局变量用来统计个数
{
    if (bt)         //判断bt是否为空
    {
        if (bt->lchild == NULL && bt->rchild == NULL)
        {
            count++;
        }
        leafnum(bt->lchild);    //递归遍历左子树
        leafnum(bt->rchild);    //递归遍历右子树
    }
}

//统计二叉树结点个数
void Nodenum(BT *bt)
{
    if (bt)
    {
        count++;        //count(初值为0)为全局变量
        Nodenum(bt->lchild);    //递归遍历左子树
        Nodenum(bt->rchild);    //递归遍历右子树
    }
}

//求二叉树的深度
int treedepth(BT *bt)
{
    int ldepth, rdepth;
    if (bt == NULL)
        return 0;
    else
    {
        ldepth = treedepth(bt->lchild);
        rdepth = treedepth(bt->rchild);
        if (ldepth > rdepth)
            return (ldepth + 1);
        else
            return (rdepth + 1);
    }
}

//查找数据元素
BT *search(BT *bt, char x)   //查找数据x
{
    if (bt->data == x)       //当查找成功时返回该结点的指针
        return bt;
    //否则,在左右子树分别查找
    if (bt->lchild != NULL)
        return (search(bt->lchild, x));
    if (bt->rchild != NULL)
        return (search(bt->rchild, x));
    return NULL;     //查找失败,返回空指针
}