《平衡二叉排序树的构建》由会员分享，可在线阅读，更多相关《平衡二叉排序树的构建（4页珍藏版）》请在金锄头文库上搜索。
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 &p)/对以*p 为根的二叉排序树做右旋处理，处理之后 p 指向新的树根结点BSTree lc;lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;vo
2、id L_Rotate(BSTree &p)/对以*p 为根的二叉排序树做左旋处理，处理之后 p 指向新的树根结点BSTree rc;rc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;void LeftBalance(BSTree &T)/对已*T 为根的二叉排序树做左平衡旋转处理BSTree lc,rd;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
3、;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 &T)/对已*T 为根的二叉排序树做右平衡旋转处理BSTree lc,rd;lc=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;c
4、ase 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,int key,bool &taller)/若在平衡二叉排序树中不存在与关键字 key 相等的结点，则将关键字插入树中/布尔变量 taller 表示树是否“长高”if(T=NULL)T=(BSTree)malloc(sizeof(BSTNode);T-data=key;T-bf=EH;/叶子结点其平衡因子肯定为 0T-lchild=T-rchild=NU
5、LL;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;els
6、e/插入右子树中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 &T)/输出结点if(T!=NULL)printf(%d ,T-data);void PreOrderTraverse(BSTree &T)/递归实现先序遍历if(T!=NULL)VistTree(T);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);
