//二叉树的操作

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

//二叉树结点结构体
typedef struct BTNode{
    char data;
    struct BTNode *lchild,*rchild;
}BTNode,*BTree;

int leafNum=0; //统计叶子结点数量

//创建二叉树
BTree CreateBitree(BTree T)//先序创建一颗二叉树
{
  char  e;
  printf("请输入结点数据:");
  scanf("%c", &e);
  fflush(stdin); //用于清空缓冲区
  if (e != '#')     //判断当前输入的字符
 {
 
   T = (BTree)malloc(sizeof(BTNode)); //分配存贮空间
   T->data = e;
   T->lchild = NULL;
   T->rchild = NULL;
   T->lchild = CreateBitree(T->lchild); //递归创建左孩子节点值
   T->rchild = CreateBitree(T->rchild);   //递归创建右孩子节点值
 }
 return T;
}

//先序遍历
void preOrder(BTree T){
    if (T)
    {
        printf("%c ",T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

//求二叉树叶子数量
void calculateLeafNum(BTree root){
    if (root==NULL)
    {
        return;
    }
    if (root->lchild==NULL&&root->rchild==NULL)
    {
        leafNum++;
    }
    calculateLeafNum(root->lchild);
    calculateLeafNum(root->rchild);
}

//求二叉树高度
int getTreehight(BTree root){
    if (root==NULL)
    {
        return 0;
    }
    //求左子树高度
    int lHight=getTreehight(root->lchild);
    //求右子树高度
    int rHight=getTreehight(root->rchild);
    //从左右子树中取高度大的+1就是该二叉树高度
    int hight=lHight>rHight?lHight+1:rHight+1;
    return hight;
}

//拷贝二叉树
BTree copyTree(BTree T){
    if (T==NULL)
    {
        return NULL;
    }
    //先拷贝左子树
    BTree lTree=copyTree(T->lchild);
    //再拷贝右子树
    BTree rTree=copyTree(T->rchild);
    //创建根节点
    BTree newTree=(BTree)malloc(sizeof(BTNode));
    //初始化新的根节点
    newTree->data=T->data;
    newTree->lchild=lTree;
    newTree->rchild=rTree;

    return newTree;
}

//释放二叉树
void freeTree(BTree T){
    if (T==NULL)
    {
        return;
    }
    //先释放左子树
    free(T->lchild);
    //再释放右子树
    free(T->rchild);
    //最后释放根节点
    printf("%c 被释放了",T->data);
    free(T);
}





int main()
{   
    BTree myTree=CreateBitree(myTree);
    //printf(" ");
    printf("先序遍历的序列是：");
    preOrder(myTree);
    printf("\n");

    calculateLeafNum(myTree);
    printf("该二叉树叶子结点数量为：");
    printf("%d\n",leafNum);

    int hight=getTreehight(myTree);
    printf("该二叉树的高度为：%d\n",hight);

    BTree newTree=copyTree(myTree); //拷贝二叉树
    preOrder(newTree);
    return 0;
}