【数据结构】二叉树的创建，遍历，求叶子数、深度。

---

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

/*==============================================
 *            仅作参考，请勿照抄
 *==============================================
 */

//创建树节点
typedef  struct  BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//建立树函数
void  CreateBiTree(BiTree &T) 
{
    char ch;
    scanf("%c", &ch);//输入节点数据
    if (ch == '#')T = NULL;//将#视为空标记
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));//分配节点内存空间
        T->data = ch;//将数据输入节点
        CreateBiTree(T->lchild);//递归左节点
        CreateBiTree(T->rchild);
    }
}


//先序遍历
void  PreOrderTraverse(BiTNode *T) 
{
    if (T)//若T不为空
    {
        printf("%c", T->data);//先访问节点数据
        PreOrderTraverse(T->lchild);//再访问左节点
        PreOrderTraverse(T->rchild);//最后访问右节点
    }
}

//中序遍历：先访问左节点，再访问节点数据，最后访问右节点
void InOrderTraverse(BiTNode *T) 
{
    if (T)
    {
        InOrderTraverse(T->lchild);
        printf("%c", T->data);
        InOrderTraverse(T->rchild);
    }
}

//后序遍历：先访问左节点，再右节点，最后访问节点数据
void PostOrderTraverse(BiTNode *T) 
{
    if (T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c", T->data);
    }
}

//获得叶子数量
//思路：1.找到叶子 2.计数
//方法一：
int GetLeavesCounts(BiTNode *T)
{
    int Count = 0;//建立（初始化）计数器
    if (!T)return 0;//若T为空，直接终止函数，返回0
    if (!T->lchild&&!T->rchild)
    {
        Count++;//当某节点为叶子（左右节点皆无），则计数器加一
    }
    else
    {
        Count += GetLeavesCounts(T->lchild);//否则，当节点有左或右孩子，则向下递归，直到找到叶子。
        Count += GetLeavesCounts(T->rchild);
    }
    return Count;//在计数器清空前返回值
}

//方法二：
/*int GetLeavesCounts(BiTNode *T)
{
    if(!T)return 0;//若节点为空，直接返回
    int LeftCount=GetLeavesCounts(T->lchild);
    int RightCount=GetLeavesCounts(T->rchild);//分别遍历左右孩子
    return (LeftCount==0&&RightCount==0)?1:LeftCount+RightCount;
    //若该节点左右孩子都是空（即该节点是一个叶子），返回1（代表这个方向有一个叶子），
    //否则该节点不是叶子，就把它左右孩子的叶子数相加。
}*///获得树深度

int GetBiTreeDepth(BiTNode *T) 
{
    if (!T)return 0;//若节点为空，直接终止函数，返回深度0
    int LeftDepth = GetBiTreeDepth(T->lchild);
    int RightDepth = GetBiTreeDepth(T->rchild);//遇到左右节点，进行递归，获得其下最大深度
    return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 1);
         //判断左右节点谁“深”，判断更深的路径加一（当前深度）后返回
    //递归到最后遇到叶子的情况(0>0)?(0+1):(0+1)，不用管谁+1，反正结果是1
}

int main()
{
    BiTree TreePointer;//声明树
    printf("Please Type the NODE of tree (type in ONE line):\n");
    CreateBiTree(TreePointer);//建立树
    printf("\nPre-Order Traverse Result:\n");
    PreOrderTraverse(TreePointer);//前序遍历
    printf("\nIn-Order Traverse Result:\n");
    InOrderTraverse(TreePointer);//中序遍历
    printf("\nPost-Order Traverse Result:\n");
    PostOrderTraverse(TreePointer);//后序遍历
    printf("\nTree Leaves Number:%d", GetLeavesCounts(TreePointer));//输出叶子数量
    printf("\nTree Depth:%d\n", GetBiTreeDepth(TreePointer));//输出深度
}