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

}//if

}//DestroyDSTable

int InitDSTable(BSTree &DT)

{ // 操作结果: 构造一个空的动态查找表DT DT=NULL; return 1; }//InitDSTable

void Visit(BSTree DT) {

//printf(\printf(\}//Visit

void TraverseDSTable(BSTree &DT,void(*Visit)(BSTree))

{ // 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数

// 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 if(DT) {

TraverseDSTable(DT->lchild,Visit); // 先中序遍历左子树 Visit(DT); // 再访问根结点

TraverseDSTable(DT->rchild,Visit); // 最后中序遍历右子树 } }

int InsertAVLD(BSTree &T) {

ElemType e; Boolean taller;

printf(\scanf(\while(e.key!=-1) {

InsertAVL(T,e,taller);

printf(\ scanf(\ }

return 1;

}//InsertAVLD

void LeftBalanceD(BSTree T,int &shorter) {

BSTree lc=T->lchild,rd; switch(lc->bf) { case LH:

T->bf=lc->bf=EH; R_Rotate(T);break; case EH:

T->bf=LH; lc->bf=RH;

R_Rotate(T);break; case RH:

rd=lc->rchild; switch(rd->bf) {

case RH:

T->bf=EH;lc->bf=LH;shorter=0;break; case EH:

T->bf=EH;lc->bf=EH;shorter=1;break; case LH:

T->bf=RH;lc->bf=EH;shorter=1;break; }//switch rd->bf=EH;

L_Rotate(T->lchild); R_Rotate(T); }//switch }//LeftBalanceD

void RightBalanceD(BSTree T,int &shorter) {

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

T->bf=rc->bf=EH; R_Rotate(T);break;

case EH:

T->bf=RH; rc->bf=RH;

L_Rotate(T);shorter=0;break; case LH:

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

case RH:

T->bf=EH;rc->bf=RH;break; case EH:

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

T->bf=LH;rc->bf=EH;break; }//switch ld->bf=EH;

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

int SearchBSTD(BSTree &T) {

ElemType e;

printf(\scanf(\