【アルゴリズム導論】二叉木の葉数と深さを求める

ツリーの葉数と深さ
二叉木の遍歴アルゴリズムは多くの二叉木演算のアルゴリズム設計の基礎であるため,遍歴アルゴリズムの応用は広範である.次に,遍歴アルゴリズムによる二叉木の葉数と深さを例に,二叉木遍歴アルゴリズムの理解を深める.
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("
");
	printf("       ：  %d",treedepth(head,l));
	printf("
");
	printf("             ：");
//	Layer(head);
	printf("
");

}

/*************************************************\
    ：     （      ）
  ：        
  ：           
\*************************************************/
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;
}

注:プログラムエラーが発生した場合、使用する開発プラットフォームのバージョンが異なる可能性があります.次のリンクをクリックしてください.説明
原文:http://blog.csdn.net/tengweitw/article/details/9792253
作者:nineheadedbird