动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）

BSTree rc,ld; rc=T->rchild; switch(rc->bf) {

case RH:

T->bf=rc->bf=EH; L_Rotate(T); break; case LH:

ld=rc->lchild; switch(ld->bf) {

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; }//switch ld->bf=EH;

R_Rotate(T->rchild); L_Rotate(T); }//switch }//RightBalance

int InsertAVL(BSTree &T,ElemType e,int &taller)

{ // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 // 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 // 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否

if(!T)

{ // 插入新结点，树“长高”，置taller为TRUE T=(BSTree)malloc(sizeof(BSTNode)); T->data=e;

T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE; } else {

if EQ(e.key,T->data.key)

{ // 树中已存在和e有相同关键字的结点则不再插入 taller=FALSE; return FALSE; }

if LT(e.key,T->data.key)

{ // 应继续在*T的左子树中进行搜索

if(!InsertAVL(T->lchild,e,taller)) // 未插入 return FALSE;

if(taller) // 已插入到*T的左子树中且左子树“长高” 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; } } else

{ // 应继续在*T的右子树中进行搜索

if(!InsertAVL(T->rchild,e,taller)) // 未插入 return FALSE;

if(taller) // 已插入到T的右子树且右子树“长高” switch(T->bf) // 检查T的平衡度 {

case LH: T->bf=EH; // 原本左子树比右子树高，现左、右子树等高 taller=FALSE; break;

case EH: // 原本左、右子树等高，现因右子树增高而使树增高 T->bf=RH; taller=TRUE; break;

case RH: // 原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; }

} }

return TRUE; }

BSTree SearchBST(BSTree T,KeyType key)

{ // 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， // 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。 if((!T)||EQ(key,T->data.key)) return T; // 查找结束

else if LT(key,T->data.key) // 在左子树中继续查找 return SearchBST(T->lchild,key); else

return SearchBST(T->rchild,key); // 在右子树中继续查找 }//SearchBST

void DestroyDSTable(BSTree &DT)

{ // 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT if(DT) // 非空树 {

if(DT->lchild) // 有左孩子

DestroyDSTable(DT->lchild); // 销毁左孩子子树 if(DT->rchild) // 有右孩子

DestroyDSTable(DT->rchild); // 销毁右孩子子树 free(DT); // 释放根结点 DT=NULL; // 空指针赋0