#define?MAX_NUM?100
#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0
#define?Status?int
#define?LH?1??//左高
#define?RH?-1?//右高
#define?EH?0??//等高
#define?TETYPE?“%c“
#define?TElemType?char
#include?
#include?
#include?
#include?
typedef?struct?BSTNode
{
	TElemType?data;
	int??????bf;????????????????????//結點的平衡因子
	struct?BSTNode?*lchild?*rchild;//左.右孩子指針
}BSTNode?*BSTree;
//***********基本操作***************************************
void?Visit（BSTree?T）
{
	printf（TETYPE?T->data）;
	printf（“（%d）“?T->bf）;
	printf（“?“）;
}
Status?BSTreeEmpty（BSTree?T）
//初始條件：平衡二叉排序樹存在。
//操作結果：若T為空平衡二叉排序樹，則返回TRUE否則FALSE.
{
	return?（T???FALSE?:?TRUE）;
}
int?BSTreeDepth（BSTree?T）
//初始條件：平衡二叉排序樹存在。操作結果：返回T的深度。
{
	int?L_depthR_depth;
	if（T==NULL）
		return?0;
	else
	{
		if（T->lchild）
			L_depth?=?BSTreeDepth（T->lchild）;
		else
			L_depth?=?0;
		if（T->rchild）
			R_depth?=?BSTreeDepth（T->rchild）;
		else
			R_depth=0;
		return?（L_depth?>=?R_depth???L_depth?:?R_depth）+1;
	}
}
int?LeafNum（BSTree?T）
//求葉子結點數，非遞歸中序遍歷
{
	BSTree?s[MAX_NUM];?int?i=0num=0;?BSTree?p;

	if（T）
	{
		s[i++]=T;
		while（i）
		{
			while（（p=s[i-1]）&&p）
				s[i++]=p->lchild;
			--i;//空指針出
			if（i）
			{
				p=s[--i];
				if（!p->lchild&&!p->rchild）
				{
					num++;
					Visit（p）;
					putchar（‘?‘）;
				}
				s[i++]=p->rchild;
			}
		}
	}
	return?num;
}
int?NodeNum（BSTree?T）
//求結點數，非遞歸中序遍歷
{
	BSTree?s[MAX_NUM];?int?i=0num=0;?BSTree?p;

	if（T）
	{
		s[i++]=T;
		while（i）
		{
			while（（p=s[i-1]）&&p）
				s[i++]=p->lchild;
			--i;//空指針出
			if（i）
			{
				p=s[--i];
				num++;
				s[i++]=p->rchild;
			}
		}
	}
	return?num;
}
void?DestoryBSTree（BSTree?*T）
//后序遍歷銷毀平衡二叉排序樹T
{
	if（*T）
	{
		if（（*T）->lchild）
			DestoryBSTree（&（*T）->lchild）;
		if（（*T）->rchild）
			DestoryBSTree（&（*T）->rchild）;
		free（*T）;
		*T?=?NULL;
	}
}
void?R_Rotate（BSTree?*p）
{//對以*p為根的平衡二叉排序樹作右旋處理，處理之后p指向新的樹根結點
?//即旋轉處理之前的左子樹的根結點
	BSTree?lc?=?NULL;

	lc?=?（*p）->lchild;????????//lc指向*p的左子樹根結點
	（*p）->lchild?=?lc->rchild;//lc的右子樹掛接為*p的左子樹
	lc->rchild?=?*p;			
	*p?=?lc;????????????????//p指向新的根結點
}
void?L_Rotate（BSTree?*p）
{//對以*p為根的平衡二叉排序樹作左旋處理，處理之后p指向新的樹根結點，
?//即旋轉處理之前的右子樹的根結點
	BSTree?rc?=?NULL;

	rc?=?（*p）->rchild;????????//rc指向*p的右子樹根結點
	（*p）->rchild?=?rc->lchild;//rc的左子樹掛接為*p的右子樹
	rc->lchild?=?*p;????????
	*p?=?rc;????????????????//p指向新的根結點
}
void?LeftBalance（BSTree?*T）
{//對以指針Ｔ所指結點為根的平衡二叉排序樹作左平衡旋轉處理，
?//本算法結束時，指針Ｔ指向新的根結點
	BSTree?lc?=?NULL?rd?=?NULL;

	lc?=?（*T）->lchild;???//lc指向*T的左子樹的樹根結點
	switch（lc->bf）???????//檢查*T的左子樹的平衡度，并作相應的平衡處理
	{
	case?LH:?????????????//新結點插入在*T的左孩子的左子樹上，要作單右旋處理
		（*T）->bf?=?lc->bf?=?EH;
		R_Rotate（T）;
		break;
	case?RH:?????????????//新結點插入在*T的左孩子的右子樹上，要作雙旋處理
		rd?=?lc->rchild;?//rd指向*T的左孩子的右子樹的根
		switch（rd->bf）???//根據其的平衡度，修改*T及其左孩子的平衡因子
		{
		case?LH:
			（*T）->bf?=?RH;
			lc->bf?=?EH;
			break;
		case?EH:
			（*T）->bf?=?l