【问题描述】

计算二叉树的深度和叶子结点数

【输入形式】

输入二叉树的先序遍历序列建立二叉树。

【输出形式】

输出二叉树的叶子结点数和深度。

【样例输入】

A

B

C

#

#

#

#

【样例输出】

Leaves:1

Depth:3

求给定二叉树的深度：

    二叉树的深度就是二叉树中结点的最大层次。如果二叉树是空树，则深度为0；否则，分别求二叉树根左子树和右子树的深度，取其中最大值加一就是该 二叉树的最大深度。

    递归计算公式为：Depth（T）={0；当T==NULL;                                                               }

                                                      {max(Depth(T->lchild),Depth(T->rchild))+1;当T！=NULL;}

如下：

int  depth(BiTree  t)
{
//此处补充代码，求取二叉树的深度
    int hl,hr;
    if(t==NULL)return 0;     //若数为空则返回0
    else
    {
        hl=depth(t->lchild);  //递归求左子树的深度
        hr=depth(t->rchild);  //递归求右子树的深度
        if(hl>hr)return (hl+1);
        else return (hr+1);
    }
}

求叶子结点数也可以通过递归的方法进行统计。

方法如下：

int  Leaves(BiTree  t)
{
//此处补充代码，统计二叉树中叶子结点数
    int count1,count2;
    if(t==NULL)return 0;   //数空
    else
        if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点
        else
        {
            count1=Leaves(t->lchild);//左子树叶子结点数
            count2=Leaves(t->rchild);//右子树叶子结点数
            return count1+count2;//返回叶子结点数
        }
}

完整带码如下：

#include  <stdio.h>
#include  <stdlib.h>
#include<malloc.h>
#define  MAX  20
//二叉链表结点定义
typedef  struct  BTNode
{
    char  data;
    struct  BTNode  *lchild;
    struct  BTNode  *rchild;
}*BiTree;

void  createBiTree(BiTree  *t)
{
//此处补充代码，完成以先序遍历方式建立二叉树
    char s;
    BiTree q;
    s=getchar();
    getchar();
    if(s=='#')
    {
        *t=NULL;
        return;
    }
    q=(BiTree)malloc(sizeof(struct BTNode));
    q->data=s;
    *t=q;
    createBiTree(&q->lchild);
    createBiTree(&q->rchild);
}
/*
void  PreOrder(BiTree  p)
{
//此处补充代码，完成二叉树的先序遍历
    if(p!=NULL)
    {
        printf("%c",p->data);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

void  InOrder(BiTree  p)
{
//此处补充代码，完成二叉树的中序遍历
    if(p!=NULL)
    {
        InOrder(p->lchild);
        printf("%c",p->data);
        InOrder(p->rchild);
    }
}

void  PostOrder(BiTree  p)
{
//此处补充代码，完成二叉树的后序遍历
    if(p!=NULL)
    {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        printf("%c",p->data);
    }
}
*/
int  Leaves(BiTree  t)
{
//此处补充代码，统计二叉树中叶子结点数
    int count1,count2;
    if(t==NULL)return 0;   //数空
    else
        if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点
        else
        {
            count1=Leaves(t->lchild);//左子树叶子结点数
            count2=Leaves(t->rchild);//右子树叶子结点数
            return count1+count2;//返回叶子结点数
        }
}

int  depth(BiTree  t)
{
//此处补充代码，求取二叉树的深度
    int hl,hr;
    if(t==NULL)return 0;     //若数为空则返回0
    else
    {
        hl=depth(t->lchild);  //递归求左子树的深度
        hr=depth(t->rchild);  //递归求右子树的深度
        if(hl>hr)return (hl+1);
        else return (hr+1);
    }
}
int  main()
{
//此处补充代码，按要求输出二叉树的叶子结点数和深度
    BiTree p;
    createBiTree(&p);
    printf("Leaves:%d\n",Leaves(p));
    printf("Depth:%d\n",depth(p));
    return  0;
}

运行结果如下：