#include?
#include?
#include
#include
#include?

#?define?LH?1?
#?define?EH?0
#?define?RH?-1
#?define?TRUE?1
#?define?FALSE?0
#?define?MAX?30
bool?taller=0;???//插入時反映樹是否長高0不長高??1長高
bool?shorter;????//刪除時時反映樹是否長高0不長高??1長高

typedef?struct?stu//學生信息
{
????int?num;?//學號
????char?name[15];?//姓名
	int?Class;?//班級
	char?sex;?//性別
	char?addr[15];??//家庭住址
}student;

typedef?struct?BSTNode??//結(jié)點結(jié)構(gòu)
{
????student?stu;
????int?bf;??//平衡因子
????struct?BSTNode?*?lchild?*?rchild;
}BSTNode?*BSTree;

BSTree?R_Rotate（BSTree?p）
{??????//?對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結(jié)點，即旋轉(zhuǎn)
???????//?處理之前的左子樹的根結(jié)點。
???BSTNode?*lc;
???lc=p->lchild;
???p->lchild=lc->rchild;
???lc->rchild=p;
???p=lc;
???return?p;
}?/*R_Rotate*/

BSTree?L_Rotate（BSTree?p）
{????//?對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結(jié)點，即旋轉(zhuǎn)
??????//?處理之前的右子樹的根結(jié)點。
???BSTNode?*rc;
???rc=p->rchild;
???p->rchild=rc->lchild;
???rc->lchild=p;p=rc;
???return?p;
}/*L_Rotate*/

BSTree?LeftBalance（BSTree?T）
{						//?對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時，
						//?指針T指向新的根結(jié)點。
???BSTNode?*lc*rd;
???lc=T->lchild;
???switch（lc->bf）
???{?????????//?檢查*T的左子樹的平衡度，并作相應(yīng)平衡處理
????case?LH:?//?新結(jié)點插入在*T的左孩子的左子樹上，要作單右旋處理
????????T->bf=lc->bf=EH;
????????T=R_Rotate（T）;
????????break;
????case?RH:???//?新結(jié)點插入在*T的左孩子的右子樹上，要作雙旋處理
????????rd=lc->rchild;
????????switch（rd->bf）
		{??????//?修改*T及其左孩子的平衡因子
????????case?LH:
????????????T->bf=RH;
????????????lc->bf=EH;
????????????break;
????????case?EH:
????????????T->bf=lc->bf=EH;
????????????break;
????????case?RH:
????????????T->bf=EH;
????????????lc->bf=LH;
????????????break;
		}
????????rd->bf=EH;
????????T->lchild=L_Rotate（T->lchild）;
????????T=R_Rotate（T）;
???}
return?T;
}

BSTree?RightBalance（BSTree?T）
{????????//?對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時，
?????????//?指針T指向新的根結(jié)點
???BSTree?rcld;
???rc=T->rchild;
???switch（rc->bf）
???{???????????????//?檢查*T的右子樹的平衡度，并作相應(yīng)平衡處理
???case?RH:????????//?新結(jié)點插入在*T的右孩子的右子樹上，要作單左旋處理
??????T->bf=rc->bf=EH;
??????T=L_Rotate（T）;
??????break;
???case?LH:????????//?新結(jié)點插入在*T的右孩子的左子樹上，要作雙旋處理
??????ld=rc->lchild;
??????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;
??????T->rchild=R_Rotate（T->rchild）;
??????T=L_Rotate（T）;
???}
???return?T;
}

BSTree?InsertAVL?（BSTree?T?BSTree?s）
{?????//?若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點，則插入一個
??????//?數(shù)據(jù)元素為e的新結(jié)點，并返回1，否則返回0。若因插入而使二叉排序樹
??????//?失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長高與否。
????BSTree?p;
????if（!T）
	{?????//?插入新結(jié)點，樹“長高”，置taller為TRUE
		T=s;
????????T->lchild=T->rchild=NULL;
????????T->bf=EH;
????????taller=TRUE;
	}
????else
	{
????????if（s->stu.num==T->stu.num）
		{?????????????//?樹中已存在和e有相同關(guān)鍵字的結(jié)點則不再插入
//			printf（“插入的學生已存在!!!“）;
????????????taller=FALSE;
????????????return?N

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

?????文件??????50176??2012-04-25?14:00??二叉平衡樹學生管理\Debug\vc60.idb

?????文件??????69632??2011-07-04?18:32??二叉平衡樹學生管理\Debug\vc60.pdb

?????文件??????66560??2011-07-03?16:36??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.bsc

?????文件?????196688??2011-07-04?18:32??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.exe

?????文件?????273056??2011-07-04?18:32??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.ilk

?????文件??????29877??2011-07-04?18:32??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.obj

?????文件?????232500??2011-07-04?17:50??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.pch

?????文件?????533504??2011-07-04?18:32??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.pdb

?????文件??????????0??2011-07-03?16:36??二叉平衡樹學生管理\Debug\二叉平衡樹學生管理.sbr

?????文件????????320??2011-07-03?16:08??二叉平衡樹學生管理\stu_list

?????文件??????14033??2011-07-04?18:32??二叉平衡樹學生管理\二叉平衡樹學生管理.cpp

?????文件???????3547??2011-07-04?17:50??二叉平衡樹學生管理\二叉平衡樹學生管理.dsp

?????文件????????561??2011-07-04?19:05??二叉平衡樹學生管理\二叉平衡樹學生管理.dsw

?????文件??????50176??2012-07-01?17:42??二叉平衡樹學生管理\二叉平衡樹學生管理.ncb

?????文件??????48640??2012-07-01?17:42??二叉平衡樹學生管理\二叉平衡樹學生管理.opt

?????文件???????1228??2011-07-04?18:32??二叉平衡樹學生管理\二叉平衡樹學生管理.plg

?????目錄??????????0??2011-07-04?18:32??二叉平衡樹學生管理\Debug

?????目錄??????????0??2012-07-01?17:42??二叉平衡樹學生管理

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

??????????????1570498????????????????????18