发布时间 : 星期五 文章动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）更新完毕开始阅读ef873a4f2b160b4e767fcfde
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