#include
#include
#include
#include
#define?TRUE??1
#define?FALSE?0
#define?LH?+1??//左高
#define?RH?-1??//右高?
#define?EH?0???//等高

typedef?struct?ElemType{
	int???key;
}ElemType;
typedef?struct?BSTNode{
	ElemType????????data;
????int????????????bf;?????????????????//結點的平衡因子
????struct?BSTNode??*lchild*rchild;????//左右孩子指針
}BSTNode*BSTree;

void??menu（）
{printf（“????????@@@@@@@@@@@@@@@@@@@@@@@平衡二叉樹操作的演示@@@@@@@@@@@@@@@@@@@@@@\n“）;?????//主界面函數
?printf（“????????@???????????????????????????????????????????????????????????????@\n“）;
?printf（“????????@??????????????????????1.創建樹?????????????????????????????????@\n“）;
?printf（“????????@??????????????????????2.查找元素???????????????????????????????@\n“）;
?printf（“????????@??????????????????????3.插入元素???????????????????????????????@\n“）;
?printf（“????????@??????????????????????4.刪除元素???????????????????????????????@\n“）;
?printf（“????????@??????????????????????5.合并樹?????????????????????????????????@\n“）;
?printf（“????????@??????????????????????6.分裂樹?????????????????????????????????@\n“）;
?printf（“????????@??????????????????????0.退出???????????????????????????????????@\n“）;
?printf（“????????@???????????????????????????????????????????????????????????????@\n“）;
?printf（“????????@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n“）;
?printf（“\n請選擇（0----6）：“）;
}
?
void?DispTree（BSTree?Tint?iint?j）{??//樹的打印輸出
	if（T->rchild）?
		DispTree（T->rchildi+4j）;
	for（j=1;j<=i;j++）?printf（“?“）;
	???printf（“%d“T->data.key）;
	???printf（“（“）;?printf（“%d“T->bf）;?printf（“）“）;
	???printf（“\n“）;
	??if（T->lchild）?
		??DispTree（T->lchildi+4j）;
}

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


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



void?LeftBalance（BSTree?&T）?{??
??//?對以指

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????50176??2010-05-27?21:23??課程設計（平衡二叉樹）\Debug\vc60.idb

?????文件??????61440??2010-05-10?15:41??課程設計（平衡二叉樹）\Debug\vc60.pdb

?????文件?????221247??2010-05-27?21:23??課程設計（平衡二叉樹）\Debug\平衡二叉樹.exe

?????文件?????288384??2010-05-27?21:23??課程設計（平衡二叉樹）\Debug\平衡二叉樹.ilk

?????文件??????25186??2010-05-27?21:23??課程設計（平衡二叉樹）\Debug\平衡二叉樹.obj

?????文件?????280856??2010-05-09?23:32??課程設計（平衡二叉樹）\Debug\平衡二叉樹.pch

?????文件?????607232??2010-05-10?15:41??課程設計（平衡二叉樹）\Debug\平衡二叉樹.pdb

?????文件??????12204??2010-05-10?14:46??課程設計（平衡二叉樹）\平衡二叉樹.cpp

?????文件???????3451??2010-05-27?21:23??課程設計（平衡二叉樹）\平衡二叉樹.dsp

?????文件????????528??2010-05-27?21:26??課程設計（平衡二叉樹）\平衡二叉樹.dsw

?????文件??????50176??2010-05-27?21:26??課程設計（平衡二叉樹）\平衡二叉樹.ncb

?????文件??????48640??2010-05-27?21:26??課程設計（平衡二叉樹）\平衡二叉樹.opt

?????文件????????766??2010-05-27?21:23??課程設計（平衡二叉樹）\平衡二叉樹.plg

?????文件?????177664??2011-05-05?22:16??課程設計（平衡二叉樹）\報告.doc

?????目錄??????????0??2011-05-05?22:15??課程設計（平衡二叉樹）\Debug

?????目錄??????????0??2011-05-05?22:18??課程設計（平衡二叉樹）

-----------?---------??----------?-----??----

??????????????1827950????????????????????16