#include“iostream.h“
#include“BBstree.h“
#include“stdlib.h“
BBstree?Search（BBstree?&TKeytype?key）
{???//在平衡二叉排序樹中查找與key值相同的關鍵字，若存在則函數返回相應的不為空的指針，
	//否則返回空指針
	if（!T||（key==T->key））
		return?T;
	else?if（keykey）
		return?Search（T->lchildkey）;??//遞歸在左子樹中進行查找
	else
		return?Search（T->rchildkey）;??//遞歸在右子樹中進行查找
}
void?L_Rotate（BBstree?&p）
{??//對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結點，及旋轉處理之前的樹的右子樹的根結點
	BBstree?rc=p->rchild;?//rc指向*p的右子樹的根結點
	p->rchild=rc->lchild;?//rc的左子樹掛接為*p的右子樹
	rc->lchild=p;?//p掛接在rc的左子樹上
	p=rc;??//p指向新的根結點
}
void?R_Rotate（BBstree?&p）
{??//對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結點，及旋轉處理之前的樹的左子樹的根結點
	BBstree?lc=p->lchild;?//rc指向*p的左子樹的根結點
	p->lchild=lc->rchild;?//rc的右子樹掛接為*p的左子樹
	lc->rchild=p;?//p掛接在rc的右子樹上
	p=lc;??//p指向新的根結點
}
void?LeftBalance（BBstree?&T）
{?//對以指針T所指結點為根的二叉樹作左平衡旋轉處理，算法結束時，指針T指向新的根結點
	BBstree?lcrd;
	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=lc->bf=EH;
					??break;
					?}
			?case?RH:{
				??????T->bf=EH;
					??lc->bf=LH;
					??break;
					?}
			?}
			?rd->bf=EH;
			?L_Rotate（T->lchild）;??//對*T的左子樹作左旋平衡處理
			?R_Rotate（T）;??//對*T作右旋平衡處理
			}
	}
}
void?LeftBalance1（BBstree?&Tbool?&taller）
{//原本T所指結點的平衡因子為1刪除T的右孩子后作左平衡旋轉處理，算法結束時，指針T指向新的根結點
	BBstree?lcrd;
	lc=T->lchild;??//lc指向*T的左子樹根結點
	switch（lc->bf）??//檢查*T的左子樹的平衡度，并做相應平衡處理
	{
	case?LH:{??//T的左孩子平衡因子為1相應的對T作右旋處理使T保持平衡
		?????T->bf=lc->bf=EH;
			?R_Rotate（T）;
			?taller=true;//對T而言樹變矮
			?break;
			}
	case?EH:{??//T的左孩子平衡因子為0相應的對T作右旋處理使T保持平衡
		?????T->bf=LH;
			?lc->bf=RH;
			?R_Rotate（T）;
			?taller=false;//對T而言樹沒變矮
			?break;
			}
	case?RH:{??//T的左孩子平衡因子為-1相應的對T作右旋處理使T保持平衡
		?????rd=lc->rchild;??//rd指向*T的左孩子的右子樹根
			?switch（rd->bf）??//修改*T及其左孩子的平衡因子
			?{
			?case?LH:{//T平衡因子變為-1T的左孩子變為0	
				??????T->bf=RH;
					??lc->bf=EH;
					??break;
					?}
			?case?EH:{//T平衡因子變為0T的左孩子變為0	
				??????T->bf=lc->bf=EH;
					??break;
					?}
			?case?RH:{//T平衡因子變為0T的左孩子變為1
				??????T->bf=EH;
					??lc->bf=LH;
					??break;
					?}
			?}
			?rd->bf=EH;
			?L_Rotate（T->lchild）;??//對*T的左子樹作左旋平衡處理
			?R_Rotate（T）;//對*T作右旋平衡處理
			?taller=true;//對T而言樹變矮
			}
	}
}
void?RightBalance（BBstree?&T）
{?//對以指針T所指結點為根的二叉樹作右平衡旋轉處理，算法結束時，指針T指向新的根結點
	BBstree?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=EH;
					??rc->bf=RH;
				

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

?????文件???????4428??2008-12-18?22:22??BBstree\BBstree.dsp

?????文件????????522??2008-12-16?22:20??BBstree\BBstree.dsw

?????文件???????1537??2008-12-29?18:04??BBstree\BBstree.h

?????文件??????66560??2010-10-26?17:58??BBstree\BBstree.ncb

?????文件??????48640??2010-10-26?17:58??BBstree\BBstree.opt

?????文件????????927??2010-03-13?23:16??BBstree\BBstree.plg

?????文件??????12002??2008-12-29?20:32??BBstree\BBstree_hanshu.cpp

?????文件???????1496??2009-01-04?17:32??BBstree\BBstree_main.cpp

?????文件?????217174??2010-03-13?23:16??BBstree\Debug\BBstree.exe

?????文件?????252360??2010-03-13?23:16??BBstree\Debug\BBstree.ilk

?????文件??????43520??2008-12-28?15:49??BBstree\Debug\BBstree.opt

?????文件?????256300??2010-03-13?23:16??BBstree\Debug\BBstree.pch

?????文件?????549888??2010-03-13?23:16??BBstree\Debug\BBstree.pdb

?????文件??????18407??2009-01-04?17:32??BBstree\Debug\BBstree_hanshu.obj

?????文件??????10701??2010-03-13?23:16??BBstree\Debug\BBstree_main.obj

?????文件??????74752??2010-03-13?23:16??BBstree\Debug\vc60.idb

?????文件??????61440??2010-03-13?23:16??BBstree\Debug\vc60.pdb

?????目錄??????????0??2011-10-15?00:53??BBstree\Debug

?????目錄??????????0??2011-10-15?00:53??BBstree

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

??????????????1620654????????????????????19