#include?“stdio.h“????
#include?“stdlib.h“???
#include?“math.h“??

#define?OK?1
#define?ERROR?0
#define?TRUE?1
#define?FALSE?0
//#define?MAXSIZE?100?/*?存儲空間初始分配量?*/

#define?LH?+1?/*??左高?*/?
#define?EH?0??/*??等高?*/?
#define?RH?-1?/*??右高?*/?

typedef?int?Status;?


/*?二叉樹的二叉鏈表結點結構定義?*/
typedef??struct?BiTNode?/*?結點結構?*/
{
????int?data;??
????int?bf;?
????struct?BiTNode?*lchild?*rchild;??
}?BiTNode?*BiTree;


/*?對以p為根的二叉排序樹作右旋處理，?*/
/*?處理之后p指向新的樹根結點，即旋轉處理之前的左子樹的根結點?*/
void?R_Rotate（BiTree?*P）
{?
????BiTree?L;
????L=（*P）->lchild;?
????（*P）->lchild=L->rchild;?
????L->rchild=（*P）;
????*P=L;?
}

/*?對以P為根的二叉排序樹作左旋處理，?*/
/*?處理之后P指向新的樹根結點，即旋轉處理之前的右子樹的根結點0??*/
void?L_Rotate（BiTree?*P）
{?
????BiTree?R;
????R=（*P）->rchild;?
????（*P）->rchild=R->lchild;?
????R->lchild=（*P）;
????*P=R;?
}

/*??對以指針T所指結點為根的二叉樹作左平衡旋轉處理?*/
/*??本算法結束時，指針T指向新的根結點?*/
void?LeftBalance（BiTree?*T）
{?
????BiTree?LLr;
????L=（*T）->lchild;?
????switch（L->bf）
????{?/*??檢查T的左子樹的平衡度，并作相應平衡處理?*/?
?????????case?LH:?/*??新結點插入在T的左孩子的左子樹上，要作單右旋處理?*/?
????????????（*T）->bf=L->bf=EH;
????????????R_Rotate（T）;
????????????break;
?????????case?RH:?/*??新結點插入在T的左孩子的右子樹上，要作雙旋處理?*/?
????????????Lr=L->rchild;?/*??Lr指向T的左孩子的右子樹根?*/?
????????????switch（Lr->bf）
????????????{?/*??修改T及其左孩子的平衡因子?*/?
????????????????case?LH:?（*T）->bf=RH;
?????????????????????????L->bf=EH;
?????????????????????????break;
????????????????case?EH:?（*T）->bf=L->bf=EH;
?????????????????????????break;
????????????????case?RH:?（*T）->bf=EH;
?????????????????????????L->bf=LH;
?????????????????????????break;
????????????}
????????????Lr->bf=EH;
????????????L_Rotate（&（*T）->lchild）;?/*??對T的左子樹作左旋平衡處理?*/?
????????????R_Rotate（T）;?/*??對T作右旋平衡處理?*/?
????}
}

/*??對以指針T所指結點為根的二叉樹作右平衡旋轉處理，?*/?
/*??本算法結束時，指針T指向新的根結點?*/?
void?RightBalance（BiTree?*T）
{?
????BiTree?RRl;
????R=（*T）->rchild;?/*??R指向T的右子樹根結點?*/?
????switch（R->bf）
????{?/*??檢查T的右子樹的平衡度，并作相應平衡處理?*/?
?????case?RH:?/*??新結點插入在T的右孩子的右子樹上，要作單左旋處理?*/?
??????????????（*T）->bf=R->bf=EH;
??????????????L_Rotate（T）;
??????????????break;
?????case?LH:?/*??新結點插入在T的右孩子的左子樹上，要作雙旋處理?*/?
??????????????Rl=R->lchild;?/*??Rl指向T的右孩子的左子樹根?*/?
??????????????switch（Rl->bf）
??????????????{?/*??修改T及其右孩子的平衡因子?*/?
????????????????case?RH:?（*T）->bf=LH;
?????????????????????????R->bf=EH;
?????????????????????????break;
????????????????case?EH:?（*T）->bf=R->bf=EH;
?????????????????????????break;
????????????????case?LH:?（*T）->bf=EH;
?????????????????????????R->bf=RH;
?????????????????????????break;
??????????????}
??????????????Rl->bf=EH;
??????????????R_Rotate（&（*T）->rchild）;?/*??對T的右子樹作右旋平衡處理?*/?
??????????????L_Rotate（T）;?/*??對T作左旋平衡處理?*/?
????}
}

/*??若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個?*