6-2 计算二叉树的叶子数

本题是计算二叉树中叶子结点的个数。

函数接口定义：

在这里描述函数接口。例如：
int num (Bptr p);

裁判测试程序样例：

#include 
#include 
typedef struct node
{
    int data;
    struct node *Lson,*Rson;
}Bnode,*Bptr;

int num (Bptr p);

Bptr creat()
{
    Bptr p;
    int x;
    scanf("%d",&x);
    if(x==0)
        return NULL;
    p=(Bptr)malloc(sizeof(Bnode));
    p->data=x;
    p->Lson=creat();
    p->Rson=creat();
    return p;
}

int main()
{
  Bptr root;    
    int k;    
    root=creat();
  k=num(root);
  printf("%dn", k);
  return 0;

}

输入样例：

3 4 1 0 0 0 2 0 0

输出样例：

2

两种方法：

方法一：

int num (Bptr p)

{
    int count=0;
    if(p!=NULL)
    {
        if(p->Lson==NULL&&p->Rson==NULL)
            count++;
        count+=num(p->Lson);
        count+=num(p->Rson);
    }
    return count;
}

方法二：

int num (Bptr p)

{
    if(p==NULL)
    {return 0;}
    if(p->Lson==NULL&&p->Rson==NULL)
           return 1;
    
    return num(p->Lson)+num(p->Rson);
}