【算法导论】求二叉树的叶子数和深度

二叉树的遍历算法是许多二叉树运算的算法设计的基础，因此遍历算法的应用很广泛。下面以遍历算法求二叉树的叶子数和深度为例，来加深对于二叉树遍历算法的理解。

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;
}