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

#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));//输出深度
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据