#include?“bstree.h“

/*
???創(chuàng)建一棵帶根結(jié)點的平衡二叉樹
???若原先的二叉樹不為空，先銷毀原先的二叉樹，再重新創(chuàng)建，并放回OK
*/
Status?CreatAVL（BSTree?&TStatus?&taller）{
	ElemType?e;
	int?count?=?0;
	if（T）????//判斷平衡二叉樹是否為空，若不空則將該樹釋放
	{
		printf（“\n之前創(chuàng)建的樹還未被銷毀，現(xiàn)在為你銷毀>>>>>>>>>>>>\n“）;
		DestroyAVL（T）;
		T=NULL;
		printf（“銷毀成功！\n\n“）;
	}
	printf（“\n■請輸入要構(gòu)造的平衡二叉樹結(jié)點的關(guān)鍵字（輸入0結(jié)束創(chuàng)建）:??“）;
	scanf（“%d“&e.key）;
	printf（“姓名：“）;
	scanf（“%s“e.name）;
	printf（“年齡：“）;
	scanf（“%d“&e.age）;
	while（e.key!=0）{
		count++;
		InsertAVL（Tetaller）;
		printf（“\n■請輸入要構(gòu)造的平衡二叉樹結(jié)點的關(guān)鍵字（輸入0結(jié)束創(chuàng)建）:??“）;
	????scanf（“%d“&e.key）;
	????printf（“姓名：“）;
	????scanf（“%s“e.name）;
	????printf（“年齡：“）;
	????scanf（“%d“&e.age）;
	}
	return?count;
}

/*
???實現(xiàn)將結(jié)點e插入到二叉樹的操作
???若二叉樹中已經(jīng)存在與e相同的結(jié)點，插入失敗，放回FALSE
???否則插入成功，放回TRUE
*/
Status?InsertAVL（BSTree?&TElemType?eStatus?&taller）{
	if（NULL==T）{???//空樹，樹長高
		T?=?（BSTree）malloc（sizeof（BSTNode））;?T->data?=?e;
		T->bf?=?EH;?T->lchild?=?NULL;?T->rchild?=?NULL;?taller?=?TRUE;
	}
	else?if（e.key?==?T->data.key）{??//存在和e相同的結(jié)點
		taller?=?FALSE;?
		return?FALSE;//未插入
	}
	else?if（e.keydata.key）{//插入到左邊
		if（!InsertAVL（T->lchildetaller））?return?FALSE;
		if（taller==TRUE）{
			switch（T->bf）{//檢查T的平衡因子
			case?LH:LeftBalance（T）;?taller?=?FALSE;?break;
				//原左高，左平衡處理
			case?EH:T->bf?=?LH;?taller?=?TRUE;?break;//原等高，變左高
			case?RH:T->bf?=?EH;?taller?=?FALSE;break;//原右高，變等高
			}
		}
	}
	else{
		if（!InsertAVL（T->rchildetaller））?return?FALSE;
		if（TRUE==taller）{
			switch（T->bf）{
			case?LH:
				T->bf?=?EH;?taller?=?FALSE;?break;
			case?EH:
				T->bf?=?RH;taller?=?TRUE;?break;
			case?RH:
				RightBalance（T）;?taller?=?FALSE;?break;
			}
		}
	}
	return?TRUE;
}

/*
???實現(xiàn)對樹T的左平衡處理
*/
void?LeftBalance（BSTree?&T）{
	BSTree?lcrd;
	lc?=?T->lchild;???//lc指向T的左孩子
	switch（lc->bf）{???//檢查T的左孩子的平衡因子，并作相應(yīng)的處理
	case?LH://LL型，需要右旋轉(zhuǎn)
		T->bf?=?lc->bf?=?EH;?R_Rotate（T）;?break;
	case?RH://LR型，作雙旋轉(zhuǎn)
		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;
		L_Rotate（T->lchild）;??//對T的左孩子作左旋轉(zhuǎn)
		R_Rotate（T）;??????????//對T作右旋轉(zhuǎn)
		break;
	}
}

/*
???實現(xiàn)對樹T的右平衡處理
*/
void?RightBalance（BSTree?&T）{
	BSTree?rcld;
	rc?=?T->rchild;
	switch（rc->bf）{
	case?RH://RR型，需要左旋轉(zhuǎn)
		T->bf?=?rc->bf?=?EH;?L_Rotate（T）;?break;
	case?LH://新結(jié)點插入在T的右孩子的左子樹上屬于RL型，做雙旋處理
		ld?=?rc->lchild;
		switch（ld->bf）{
		case?LH:T->bf?=?EH;?rc->bf?=?RH;?break;
		case?EH:rc->bf?=?T->bf?=?EH;?break;
		case?RH:T->bf?=?LH;?rc->bf?=?EH;?break;
		}
		ld->bf?=?EH;
		R_Rotate（T->rchild）;//對T的右孩子作右旋轉(zhuǎn)調(diào)整
		L_Rotate（T）;????????//對T作左旋轉(zhuǎn)調(diào)整
		break;
	}
}

/*
???實現(xiàn)對最小失衡子樹的左旋轉(zhuǎn)調(diào)整
*/
void?L_Rotate（BSTree?&p）{
	BSTree?rc?=?p->rchild;
	p->rchild?=?rc->lchild;
	rc->lchild?=?p;
	p?=?rc;
}

/*
???實現(xiàn)對最小失衡子樹的右旋轉(zhuǎn)調(diào)整
*/
void?R_Rotate（BSTree?&p）{
	BSTree?lc?=?p->lchild;
	p->lchild?=?lc->rchild;
	lc->rchild?=?p;
	p?=?lc;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-01-05?09:16??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\
?????目錄???????????0??2015-12-26?14:34??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\
?????文件???????17759??2015-12-26?13:02??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\bstree.obj
?????文件???????13915??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\main.obj
?????文件???????50176??2015-12-26?13:12??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\vc60.idb
?????文件???????53248??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\vc60.pdb
?????文件??????184397??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.exe
?????文件??????264240??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.ilk
?????文件??????186988??2015-12-25?14:12??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.pch
?????文件??????476160??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\Debug\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.pdb
?????文件????????8825??2015-12-26?12:52??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\bstree.cpp
?????文件????????1365??2015-12-26?13:02??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\bstree.h
?????文件????????3839??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\main.cpp
?????文件????????4516??2015-12-25?16:52??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.dsp
?????文件?????????540??2015-12-25?13:20??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.dsw
?????文件???????50176??2015-12-26?13:31??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.ncb
?????文件???????48640??2015-12-26?13:31??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.opt
?????文件????????1338??2015-12-26?13:11??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.plg
?????文件??????446418??2016-01-05?09:16??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告.docx