二叉树的叶子数和深度
二叉树的遍历算法是许多二叉树运算的算法设计的基础，因此遍历算法的应用很广泛。下面以遍历算法求二叉树的叶子数和深度为例，来加深对于二叉树遍历算法的理解。
1. 统计二叉树中的叶子结点数
因为叶子结点是二叉树中那些左孩子和右孩子均不存在的结点，所以可在二叉树的遍历过程中，对这种特殊结点进行计数，来完成对叶子结点数的统计。这个统计可在任何一种遍历方式下给出，下面是利用 中序遍历来实现的算法：
1. 统计二叉树中的叶子结点数
因为叶子结点是二叉树中那些左孩子和右孩子均不存在的结点，所以可在二叉树的遍历过程中，对这种特殊结点进行计数，来完成对叶子结点数的统计。这个统计可在任何一种遍历方式下给出，下面是利用 中序遍历来实现的算法：
/**********************************************\
函数功能：计算叶子节点个数
输入： 二叉树的根节点
输出： 叶子节点个数
\**********************************************/
int countleaf(bitree *p)
{
static int count=0;//注意这里是静态变量，也可以改为全局变量
if(p!=NULL)
{
count=countleaf(p->lchild);
if((p->lchild==NULL)&&(p->rchild==NULL))
count=count+1;
count=countleaf(p->rchild);
}
return count;
}
2.求二叉树的深度
二叉树的深度是二叉树中结点层次的最大值。可通过先序遍历来计算二叉树中每个结点的层次, 其中的最大值即为二叉树的深度。
具体算法如下：
/**********************************************\
函数功能：计算树的深度
输入： 二叉树的根节点、当前树的深度
输出： 树的深度
\**********************************************/
int treedepth(bitree*p,int l)
{
static int h=0;
if(p!=NULL)
{
l++;
if(l>h)
h=l;
h=treedepth(p->lchild,l);
h=treedepth(p->rchild,l);
}
return h;
}
两者的完整实例如下：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define maxsize 20
typedef int datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;
void Layer(bitree *p);
bitree* CreatBitree(int* arrayA,int n);
int countleaf(bitree *p);
int treedepth(bitree*p,int l);
void main()
{
int arrayA[10]={0,1,2,3,4,5,6,7,8,9};//第一个节点没有用于存储数据
int n=sizeof(arrayA)/sizeof(int);
int l=0;//二叉树的深度
bitree *head=NULL;
head=CreatBitree(arrayA,n);
printf("二叉树的叶子数为：%d",countleaf(head));
printf("\n");
printf("二叉树的深度为： %d",treedepth(head,l));
printf("\n");
printf("按广度优先搜索遍历的结果为：");
// Layer(head);
printf("\n");
}
/*************************************************\
函数功能：建立二叉树（按照顺序方式）
输入： 原始数组
输出： 二叉树的头结点
\*************************************************/
bitree* CreatBitree(int* arrayA,int n)//顺序存储 建立二叉树
{
bitree *root;
bitree *queue[maxsize];
bitree *p;
int front,rear;
front=1;rear=0;
root=NULL;
for(int i=1;i<n;i++)
{
p=(bitree*)malloc(sizeof(bitree));
p->data=arrayA[i];
p->lchild=NULL;
p->rchild=NULL;
rear++;
queue[rear]=p;
if(rear==1)
root=p;
else
{
if(i%2==0)
queue[front]->lchild=p;
else
{
queue[front]->rchild=p;
front=front+1;
}
}
}
return root;
}
/**********************************************\
函数功能：计算叶子节点个数
输入： 二叉树的根节点
输出： 叶子节点个数
\**********************************************/
int countleaf(bitree *p)
{
static int count=0;//注意这里是静态变量，也可以改为全局变量
if(p!=NULL)
{
count=countleaf(p->lchild);
if((p->lchild==NULL)&&(p->rchild==NULL))
count=count+1;
count=countleaf(p->rchild);
}
return count;
}
/**********************************************\
函数功能：计算树的深度
输入： 二叉树的根节点、当前树的深度
输出： 树的深度
\**********************************************/
int treedepth(bitree*p,int l)
{
static int h=0;
if(p!=NULL)
{
l++;
if(l>h)
h=l;
h=treedepth(p->lchild,l);
h=treedepth(p->rchild,l);
}
return h;
}注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接：
解释说明
