1、-平衡二叉排序树的构建-#include#include#define LH +1/左边高#define EH 0/一样高#define RH -1/右边高typedef struct BSTNodeint data;int bf;/平衡因子struct BSTNode *lchild,*rchild;BSTNode,*BSTree;/平衡二叉排序树结构的定义void R_Rotate(BSTree lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;void L_Rotate(BSTree rc=p-rchild;p-rchild=rc-lchil
2、d;rc-lchild=p;p=rc;void LeftBalance(BSTree lc=T-lchild;switch(lc-bf)case LH:T-bf=lc-bf=EH;R_Rotate(T);break;case RH:rd=lc-rchild;switch(rd-bf)case LH:T-bf=RH;lc-bf=EH;break;case EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=RH;break;rd-bf=EH;L_Rotate(T-lchild);R_Rotate(T);void RightBalance(BSTree lc=
3、T-rchild;switch(lc-bf)case RH:T-bf=lc-bf=EH;L_Rotate(T);break;case LH:rd=lc-lchild;switch(rd-bf)case RH:T-bf=LH;lc-bf=EH;break;case LH:T-bf=EH;lc-bf=RH;break;case EH:T-bf=lc-bf=EH;break;rd-bf=EH;R_Rotate(T-rchild);L_Rotate(T);int InsertAVL(BSTree T-data=key;T-bf=EH;/叶子结点其平衡因子肯定为 0T-lchild=T-rchild=N
4、ULL;taller=1;/树长高了elseif(key=T-data)/如果树中已存放此关键字则不予插入taller=0;return 0;if(keydata)/关键字小于根结点则插入其左子树中if(!InsertAVL(T-lchild,key,taller)return 0;if(taller)/如果树长高了，判断是否平衡switch(T-bf)case LH:LeftBalance(T);/不平衡时调用左平衡函数，使左子树平衡taller=0; break;case EH:T-bf=LH;taller=1;break;case RH:T-bf=EH;taller=0;break;el
5、se/插入右子树中if(!InsertAVL(T-rchild,key,taller)return 0;if(taller)switch(T-bf)case LH:T-bf=EH; taller=0;break;case EH:T-bf=RH;taller=1;break;case RH:RightBalance(T);taller=0;break;return 1;void VistTree(BSTree void PreOrderTraverse(BSTree if(T-lchild)PreOrderTraverse(T-lchild);if(T-rchild)PreOrderTraverse(T-rchild);int main(void)BSTree T;bool taller=0;int i;T=NULL;for(i=1;ibf);printf(“n“);
