统计二叉树中叶子节点的数目

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
 
typedef struct Node
{
    ElemType data;
    Node *Lchild,*Rchild;
} BiTNode,*BiTree;
 
int ans=0;
BiTree CreateBiTree();//建立二叉树
void Leaf1(BiTree T);//后序遍历统计叶子节点数目
int Leaf2(BiTree T);//分治法统计叶子节点数目
 
int main(void)
{
    BiTree root=CreateBiTree();
    int count=Leaf2(root);
    printf("%d\n",count);
    Leaf1(root);
    printf("%d\n",ans);
    return 0;
}
 
BiTree CreateBiTree()//建立二叉树
{
    ElemType x;
    BiTree T;
    scanf("%c",&x);
    if(x=='#')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=x;
        T->Lchild=CreateBiTree();
        T->Rchild=CreateBiTree();
    }
    return T;
}
 
void Leaf1(BiTree T)//后序遍历统计叶子节点数目
{
    if(T!=NULL)
    {
        Leaf1(T->Lchild);
        Leaf1(T->Rchild);
        if(T->Lchild==NULL&&T->Rchild==NULL)
            ans++;
    }
}
 
int Leaf2(BiTree T)//分治法统计叶子节点数目
{
    int count;
    if(T==NULL)
        count=0;
    else if(T->Lchild==NULL&&T->Rchild==NULL)
        count=1;
    else
        count=Leaf2(T->Lchild)+Leaf2(T->Rchild);
    return count;
}
赞赏

微信赞赏支付宝赞赏

98 次阅读量

发表评论