平衡二叉排序树的构建

《平衡二叉排序树的构建》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、----------------------平衡二叉排序树的构建-------------------#include#include#defineLH+1//左边高#defineEH0//一样高#defineRH-1//右边高typedefstructBSTNode{intdata;intbf;//平衡因子structBSTNode*lchild,*rchild;}BSTNode,*BSTree;//平衡二叉排序树结构的定义voidR_Rotate(BSTree&p){//对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结

2、点BSTreelc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}voidL_Rotate(BSTree&p){//对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}voidLeftBalance(BSTree&T){//对已*T为根的二叉排序树做左平衡旋转处理BSTreelc,rd;lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=

3、EH;R_Rotate(T);break;caseRH:rd=lc->rchild;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=RH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);}}voidRightBalance(BSTree&T){//对已*T为根的二叉排序树做右平衡旋转处理BSTreelc,rd;lc=T->rchild;switch(lc->bf){caseR

4、H:T->bf=lc->bf=EH;L_Rotate(T);break;caseLH:rd=lc->lchild;switch(rd->bf){caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);L_Rotate(T);}}intInsertAVL(BSTree&T,intkey,bool&taller){//若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中

5、//布尔变量taller表示树是否“长高”if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;//叶子结点其平衡因子肯定为0T->lchild=T->rchild=NULL;taller=1;//树长高了}else{if(key==T->data){//如果树中已存放此关键字则不予插入taller=0;return0;}if(keydata){//关键字小于根结点则插入其左子树中if(!InsertAVL(T->lchild,key,taller))return0;if(taller

6、){//如果树长高了，判断是否平衡switch(T->bf){caseLH:LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡taller=0;break;caseEH:T->bf=LH;taller=1;break;caseRH:T->bf=EH;taller=0;break;}}}else{//插入右子树中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH:T->bf=EH;taller=0;break;caseEH:T->bf=RH;taller=

7、1;break;caseRH:RightBalance(T);taller=0;break;}}}}return1;}voidVistTree(BSTree&T){//输出结点if(T!=NULL)printf("%d",T->data);}voidPreOrderTraverse(BSTree&T){//递归实现先序遍历if(T!=NULL)VistTree(T);if(T->lchild)PreOrderTraverse(T->lchild);if(T->rchild)PreOrderTraverse(T->rchild)