例题：设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法

例题：设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法

如有谬误或者不足还请批评指正！

（1）统计二叉树中度为0、1、2的结点个数

int num_0 = 0, num_1 = 0, num_2 = 0;

void CountNode(BiTree T)
{
	if (T == NULL)
		return;
	if ((T->lchild && !T->rchild) || (!T->lchild && T->rchild))
		num_1++;
	else if (!T->lchild && !T->rchild)
		num_0++;
	else
		num_2++;
	CountNode(T->lchild);
	CountNode(T->rchild);
}

（2）统计二叉树的高度

int CountHeight(BiTree T)
{
	if (T == NULL)
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1;
	return Max(CountHeight(T->lchild), CountHeight(T->rchild)) + 1;
}

（3）统计二叉树的宽度

int MaxWidth = -1;
int Level[MaxSize];

void CountWidth(BiTree T, int l)
{
	if(T == NULL)
		return;
	Level[l]++;
	if(MaxWidth < Level[l])
		MaxWidth = Level[l];
	CountWidth(T->lchild, l+1);
	CountWidth(T->rchild, l+1);
}

（4）从二叉树中删去所有叶结点

void DeleteLeafNode(BiTree T)
{
	if(T == NULL)
		return;
	if(T->lchild != NULL)
	{
		BiTNode *p = T->lchild;
		if(p->lchild == NULL && p->rchild == NULL)
		{
			free(p);
			T->lchild = NULL;
		}
	}
	if(T->rchild != NULL)
	{
		BiTNode *q = T->rchild;
		if(q->lchild == NULL && q->rchild == NULL)
		{
			free(q);
			T->rchild = NULL;
		}
	}
	DeleteLeafNode(T->lchild);
	DeleteLeafNode(T->rchild);
}

（5）计算指定结点*p所在的层次

int FindNodeLevel(BiTree T, BiTNode *p, int level)
{
	if (T == NULL)
		return 0;
	if (T->data == p->data)
		return level;
	FindNodeLevel(T->lchild, p, level + 1);
	FindNodeLevel(T->rchild, p, level + 1);
	return -1;
}

（6）计算二叉树各结点中的最大元素的值

int Max = -32767;

void FindMaxNode(BSTree T)
{
	if (T != NULL)
	{
		if (Max < T->data)
			Max = T->data;
		FindMaxNode(T->lchild);
		FindMaxNode(T->rchild);
	}
}

（7）交换二叉树中每个结点的两个子女

void ExchangeNode(BiTree T)
{
	if (T == NULL)
		return;
	BiTNode *p = T->lchild;
	T->lchild = T->rchild;
	T->rchild = p;
	ExchangeNode(T->lchild);
	ExchangeNode(T->rchild);
}

（8）以先序次序输出一颗二叉树中所有结点的数据值及结点所在的层次

void PreOrder(BiTree T, int level)
{
	if (T == NULL)
		return;
	printf("T->data : %d ", T->data);
	printf("level : %d ", level);
	PreOrder(T->lchild, level + 1);
	PreOrder(T->rchild, level + 1);
}