资源描述：
《平衡二叉树举例实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、平衡二叉树举例实现Thecube,41063625(3453),canbepermutedtoproducetwoothercubes:56623104(3843)and66430125(4053).Infact,41063625isthesmallestcubewhichhasexactlythreepermutationsofitsdigitswhicharealsocube.Findthesmallestcubeforwhichexactlyfivepermutationsofitsdigitsarecube.就是找出一个最小的数使它满足，这个数的5次方的数字也是是另外4个数五次
2、方值的数字的组合。#include#include#defineLH1#defineEH0#defineRH-1typedefstructBSTNode{chars[20];intnum;intcount;intbf;structBSTNode*left,*right;}BSTNode,*BSTree;voidvisit(chars[],BSTreep){sprintf(s,"(%s)",p->s);}//右旋转voidR_Rotate(BSTree&p){BSTreelc=p->left;p->left=lc->right;lc->right=p
3、;p=lc;}//左旋转voidL_Rotate(BSTree&p){BSTreerc=p->right;p->right=rc->left;rc->left=p;p=rc;}//左平衡旋转处理voidLeftBalance(BSTree&T){BSTreelc,rd;lc=T->left;switch(lc->bf){caseLH:lc->bf=EH;T->bf=EH;break;caseRH:rd=lc->right;switch(rd->bf){caseLH:lc->bf=EH;T->bf=RH;break;caseEH://此时是rd没有左右结点lc->bf=EH;T->bf=
4、EH;break;caseRH:lc->bf=LH;T->bf=EH;}//switchrd->bf=EH;L_Rotate(T->left);//此处不可写成lc}//switchR_Rotate(T);}//右平衡旋转处理voidRightBalance(BSTree&T){BSTreerc,ld;rc=T->right;switch(rc->bf){caseLH:ld=rc->left;switch(ld->bf){caseLH:T->bf=EH;rc->bf=RH;break;caseEH:T->bf=EH;rc->bf=EH;break;caseRH:T->bf=LH;rc-
5、>bf=EH;}//switchld->bf=EH;R_Rotate(T->right);//此处不可写成rcbreak;caseRH:rc->bf=EH;T->bf=EH;}//switchL_Rotate(T);}//插入之后使其长高了则返回true,否则返回falseboolInsertAVL(BSTree&T,chars[],intnum,BSTree&p){booltaller;if(T==NULL){T=newBSTNode;strcpy(T->s,s);T->num=num;T->count=1;T->bf=EH;T->left=NULL;T->right=NULL;p=
6、T;taller=true;}//ifelse{intt;taller=false;t=strcmp(s,T->s);if(t==0){T->count++;p=T;}//ifelseif(t<0){//插入到左树中if(InsertAVL(T->left,s,num,p)){switch(T->bf){caseLH:LeftBalance(T);break;caseEH:T->bf=LH;taller=true;break;caseRH:T->bf=EH;}//switch}//if}//ifelse{//插入到右树中if(InsertAVL(T->right,s,num,p)){s
7、witch(T->bf){caseLH:T->bf=EH;break;caseEH:T->bf=RH;taller=true;break;caseRH:RightBalance(T);}//switch}//if}//else}//elsereturntaller;}voidrealse(BSTree&h){if(h){realse(h->left);realse(h->right);deleteh;}}voidshift(chars[],do
