二叉樹（二）——周遊、深度統計、葉子結點統計、結點統計

1.二叉樹的相關算法的實作（連結清單）。

#include <stdio.h>
#include <malloc.h>

#define NULL	0

typedef struct tree
{
	int data;
	struct tree *left, *right;
}ElemBT;

void create_btree(ElemBT *root, int list[], int n) /*n表示list數組中元素的個數*/
{
	int i;
	ElemBT *current, *parent, *p;

	for(i = 1; i < n; i++)
	{
		p = (ElemBT *)malloc(sizeof(ElemBT));
		p->left = p->right = NULL;
		p->data = list[i];
		current = root;
		while(current != NULL)
		{
			parent = current;
			if(current->data > p->data)
				current = current->left;
			else
				current = current->right;
		}
		if(parent->data > p->data)
			parent->left = p;
		else
			parent->right = p;
	}
}

void pre_order(ElemBT *root) /*前序周遊*/
{
	if(root) /*root != NULL*/
	{
		printf("%4d", root->data); /*根結點列印*/
		pre_order(root->left); /*左子樹周遊*/
		pre_order(root->right); /*右子樹周遊*/
	}
	else
	{
		return;
	}
}

void in_order(ElemBT *root) /*中序周遊*/
{
	if(root) /*root != NULL*/
	{
		in_order(root->left); /*左子樹周遊*/
		printf("%4d", root->data); /*根結點列印*/
		in_order(root->right); /*右子樹周遊*/
	}
	else
	{
		return;
	}
}

void post_order(ElemBT *root) /*後序周遊*/
{
	if(root) /*root != NULL*/
	{
		post_order(root->left); /*左子樹周遊*/
		post_order(root->right); /*右子樹周遊*/
		printf("%4d", root->data); /*根結點列印*/
	}
	else
	{
		return;
	}
}

int node_count(ElemBT *root) /*二叉樹結點個數統計*/
{
	int cnt = 0;
	
	if(root)
	{
		cnt += node_count(root->left);
		cnt += node_count(root->right);
		cnt ++; /*根節點*/
	}

	return cnt;
}

/*
int node_count(ElemBT *root) //結點個數統計
{
	if(root == NULL)
		return 0;
	else
		return (node_count(root->right)+node_count(root->left)+1);
}
*/

int btree_depth(ElemBT *root) /*二叉樹的深度*/
{
	int d1 = 0, d2 = 0;

	if(root == NULL)
		return 0;
	else
	{
		d1 = btree_depth(root->left);
		d2 = btree_depth(root->right);
		return (d1>d2 ? d1+1 : d2+1);
	}
}

int leaf_count(ElemBT *root) /*統計葉子結點個數*/
{
	if(!root)
		return 0;

	if(!root->left && !root->right)
		return 1;
	else
		return (leaf_count(root->left)+leaf_count(root->right));
}

int main()
{
	int list[7] = {30, 18, 16, 25, 34, 7, 31};
	ElemBT *root;

	root = (ElemBT *)malloc(sizeof(ElemBT));
	root->data = list[0];
	root->left = root->right = NULL;
	create_btree(root, list, 7);

	printf("pre_order:\n");
	pre_order(root);
	printf("\n");

	printf("in_order:\n");
	in_order(root);
	printf("\n");

	printf("post_order:\n");
	post_order(root);
	printf("\n");

	printf("Node number is: %d\n", node_count(root));
	printf("Btree depth is: %d\n", btree_depth(root));
	printf("Leaf node number is: %d\n", leaf_count(root));
	return 0;
}
           

程式運作截圖：

2.結論

（1）通過一棵二叉樹的前序、中序、後序中任意兩個的通路順序可以唯一的确定一棵二叉樹。

假設有二叉樹的中序和後序通路順序分别為：

中序：c, b, d, e, a, g, i, h, j, f

後序：c, e, d, b, i, j, h, g, f, a

分析：由後序周遊最末一個是a可以知道a為該樹的根，再結合中序可知道c, b, d, e為其左子樹，g, i, h, j, f為其右子樹。又結合後序通路可以知道b, f分别為為a的左子女和右子女，再結合中序周遊可以知道b的左子女個數為1，右子女個數為2，f的左子女個數為4，右子女個數為0。依次類推可以得到如下的二叉樹：

                              a

                         /          \

                     b                  f

                 /     \           /       

              c          d       g

                           \        \

                            e          h

                                       /   \           

                                     i       j