#include <stdio.h>
#include <stdlib.h>
 
typedef struct TNode{
    int data;
    struct TNode *lchild,*rchild;
}TreeNode,*Tree;

/*
在这段代码中，递归函数 `CreateTree` 在执行 `return` 语句后，会立即返回到调用它的上一层递归调用。
但是，整个递归过程并没有结束，仍然会继续执行后续的递归调用。
当 `CreateTree` 函数中执行 `return` 语句时，它会返回到上一层递归调用的位置，
并继续执行那个位置之后的代码。这是因为递归函数是通过函数调用栈来实现的，
每次递归调用都会在栈中创建一个新的帧，保存函数的局部变量和执行位置。
当递归函数执行完毕后，会从栈中弹出该帧，返回到上一层递归调用的位置，并继续执行。
因此，虽然在某一层递归调用中执行了 `return` 语句，但整个递归过程仍会继续执行，
直到所有的递归调用都执行完毕并返回。
*/ 

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左子节点：",x);
        CreateTree(T->lchild);
        printf("输入%d的右子节点：",x);
        CreateTree((T->rchild));
    }
}

//先序遍历二叉树(递归实现)
void PreOrderTree(Tree T)
{
    if (T==NULL)
    {
        return;
    }
    else
    {
        printf("%d ",T->data);
        PreOrderTree(T->lchild);
        PreOrderTree(T->rchild);
    }
}

//中序遍历二叉树(递归实现)
void MidOrderTree(Tree T)
{
    if(T==NULL)    
    {
        return;
    }
    else
    {
        MidOrderTree(T->lchild);
        printf("%d ",T->data);
        MidOrderTree(T->rchild);
    }
} 

//后序遍历二叉树(递归实现)
void LatOrderTree(Tree T)
{
    if(T==NULL)    
    {
        return;
    }
    else
    {
        LatOrderTree(T->lchild);
        LatOrderTree(T->rchild);
        printf("%d ",T->data);
    }
} 

int TreeDeep(Tree T)
{
    int deep=0;
    if(T)
    {
        int leftdeep=TreeDeep(T->lchild);
        int rightdeep=TreeDeep(T->rchild);
        deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
    }
    return deep;
} 

//二叉树的深度(递归实现) 
int TreeDeep(Tree T)
{
    int deep = 0;
    if (T != NULL)
    {
        int leftdeep = TreeDeep(T->lchild);
        int rightdeep = TreeDeep(T->rchild);
        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;
    }
    return deep;
}

/*
在这个函数中，`count`需要使用`static`修饰是因为它需要在递归调用中保持其值的持久性。
当函数被递归调用时，每次调用都会创建一个新的局部变量`count`，并且在递归返回时，它们的值会被销毁。
这意味着每次递归调用时，`count`的值都会被重置为0，无法正确地计算叶子节点的数量。
通过使用`static`修饰符，变量`count`的生命周期被扩展到整个程序的执行过程中，而不是局限于函数的单次调用。这样，每次递归调
用时，`count`的值会被保留下来，并能够正确地累加叶子节点的数量。
*/
//叶子节点个数(递归实现)
int LeafCount(Tree T)
{
    static int count;
    if (T != NULL)
    {
        if (T->lchild == NULL && T->rchild == NULL)
        {
            count++;
        }
        
        LeafCount(T->lchild);
        LeafCount(T->rchild);
    }
    
    return count;
}

//销毁二叉树(递归方法) 
void DestroyTree(Tree &T) {
    if (T) {
        DestroyTree(T->lchild);
        DestroyTree(T->rchild);
        free(T);
    }
}

int main()
{
    Tree T;
    CreateTree(T);
//    PreOrderTree(T);
//    MidOrderTree(T);    
    LatOrderTree(T);
    
    printf("\n");
    printf("树的深度为：%d\n",TreeDeep(T));
    printf("叶子结点的个数%d\n",LeafCount(T));
    return 0; 
}