二叉樹統計問題彙總

#include <stdio.h>
#include <stdlib.h>
#define N 100

/*二叉樹非遞歸*/ 
typedef struct btnode
{
	char data;
	btnode *lchild;
	btnode *rchild; 
}btnode;

int i=0;
int aa[]={55,10,7,-1,-1,22,-1,-1,66,-1,100,-1,-1};
char bt[]={'a','b','c','#','#','d','g','#','#','#','e','f','#','#','#'}; 
/*求二叉樹的節點數*/
int count_1(btnode *bt)
{
	if(bt == NULL) return 0;
	else
	{
		int a,b;
		a=count_1(bt->lchild);
		b=count_1(bt->rchild);
		return a+b+1;
	}
} 

/*求二叉樹的葉子節點數*/
int count_2(btnode *bt)
{
	if(bt==NULL) return 0;
	if(bt->lchild==NULL && bt->rchild==NULL) return 1;
	else
	{
		int a,b;
		a=count_2(bt->lchild);
		b=count_2(bt->rchild);
		return a+b;
	}
} 

/*求二叉樹單分支節點數*/
int count_3(btnode *bt)
{
	if(bt==NULL) return 0;
	else if((bt->lchild==NULL && bt->rchild!=NULL) || (bt->rchild==NULL && bt->lchild !=NULL)) 
	{
		int a,b;
		a=count_3(bt->lchild);
		b=count_3(bt->rchild);
		return a+b+1;
	}
	else
	{
		int a,b;
		a=count_3(bt->lchild);
		b=count_3(bt->rchild);
		return a+b;
	}
}

/*求二叉樹雙分支節點數*/
int count_4(btnode *bt)
{
	int a,b;
	if(bt==NULL) return 0;
	else if(bt->lchild!=NULL && bt->rchild!=NULL)
	{
		return count_4(bt->lchild)+count_4(bt->rchild)+1; 
	}
	else
	{
		a=count_4(bt->lchild);
		b=count_4(bt->rchild);
		return a+b; 
	}
} 

/*二叉樹的各節點子孫數*/
int count_5(btnode *bt)
{
	if(bt==NULL) return 0;
	else
	{
		int a=0,b=0;
		if(bt->lchild!=NULL)a=count_5(bt->lchild)+1;
		if(bt->rchild!=NULL)b=count_5(bt->rchild)+1;
		printf("結點%c的子孫數是：%d\n",bt->data,a+b);
		return a+b;
	}
} 

/*求二叉樹的高度*/
int count_6(btnode *bt)
{
	if(bt==NULL) return 0;
	else
	{
		int a,b;
		a=count_6(bt->lchild);
		b=count_6(bt->rchild);
		return (a>b?a:b)+1;
	} 
} 

/*求二叉樹的寬度*/
int count_7(btnode *bt)
{
	btnode *que[N];
	int front=0,rear=0;
	int size,max;
	int k;
	que[++rear]=bt;
	k=rear;
	size=rear-front;
	max=size;
	while(rear!=front)
	{
		bt=que[++front]; 
		if(bt->lchild) que[++rear]=bt->lchild;
		if(bt->rchild) que[++rear]=bt->rchild;
		if(front==k) 
		{
			size=rear-k;
			k=rear;
		}
		if(size>max) max=size;
	}
	return max;
}

/*遞歸建立二叉樹*/
btnode* tree()
{ 
	if(a[i]=='#')
	{
		i++;return NULL;
	} 
	else
	{
		btnode *bt=(btnode*)malloc(sizeof(btnode));
	
		bt->data=a[i++];
		bt->lchild=tree();
		bt->rchild=tree();
		return bt;
	} 
	
}

/*遞歸建立樹*/ 

int main()
{
	btnode *bt;
	bt=tree();

	int cnt_1;
	cnt_1=count_1(bt);
//	printf("%d",cnt_1);
	
	int cnt_2;
	cnt_2=count_2(bt);
//	printf("%d",cnt_2);
	
	int cnt_3;
	cnt_3=count_3(bt);
//	printf("%d",cnt_3);
	
	int cnt_4;
	cnt_4=count_4(bt);
//	printf("%d",cnt_4);
	
//	count_5(bt);
	
	int cnt_6;
	cnt_6=count_6(bt);
//	printf("%d",cnt_6);
	
	int cnt_7;
	cnt_7=count_7(bt);
//	printf("%d",cnt_7);

	return 0;
}