【问题描述】
计算二叉树的深度和叶子结点数
【输入形式】
输入二叉树的先序遍历序列建立二叉树。
【输出形式】
输出二叉树的叶子结点数和深度。
【样例输入】
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;
}
运行结果如下: