实习六：平衡二叉树

实验报告题目：平衡二叉树操作的演示一．需求分析利用平衡二叉树实现一个动态查找表。实现动态查找表的三种基本功能：查找、插入和删除。测试数据:13,24,37,90,53二．详细设计#includecstdio#includecstring#includecstdlib#includeiostream#includealgorithm#defineSUCCESS0#defineERROR-1#definemax(a,b)((a)(b)?(a):(b))#defineNOT_FOUND1usingnamespacestd;typedefintStatus;typedefstruct_AVL{intdata,count;inth;struct_AVL*lch,*rch;StatusInit(intd){data=d;h=count=1;lch=rch=NULL;returnSUCCESS;}}AVL,*PAVL;intGetHeight(PAVLp){if(p==NULL)return0;returnp-h;}voidUpdateHeight(PAVL&p){p-h=max(GetHeight(p-lch),GetHeight(p-rch))+1;}voidL_Rotate(PAVL&p){if(p-rch!=NULL){PAVLtmp=p-rch;p-rch=tmp-lch;tmp-lch=p;p=tmp;UpdateHeight(p-lch);UpdateHeight(p);}}voidR_Rotate(PAVL&p){if(p-lch!=NULL){PAVLtmp=p-lch;p-lch=tmp-rch;tmp-rch=p;p=tmp;UpdateHeight(p-rch);UpdateHeight(p);}}voidRightBalance(PAVL&p){if(p!=NULL)if(GetHeight(p-rch)-GetHeight(p-lch)1)//左旋{if(GetHeight(p-rch-lch)GetHeight(p-rch-rch))//双旋R_Rotate(p-rch);L_Rotate(p);}}voidLeftBalance(PAVL&p){if(p!=NULL)if(GetHeight(p-lch)-GetHeight(p-rch)1)//右旋{if(GetHeight(p-lch-rch)GetHeight(p-lch-lch))//双旋L_Rotate(p-lch);R_Rotate(p);}}StatusAVLInsert(PAVL&p,intelem){if(p==NULL){p=newAVL;if(!p)returnERROR;p-Init(elem);returnSUCCESS;}else{if(elemp-data){if(AVLInsert(p-rch,elem)==ERROR)returnERROR;RightBalance(p);}elseif(elemp-data){if(AVLInsert(p-lch,elem)==ERROR)returnERROR;LeftBalance(p);}elsep-count++;}UpdateHeight(p);returnSUCCESS;}PAVLFindSuccession(PAVL&p){PAVLr=p;if(p-lch!=NULL){r=FindSuccession(p-lch);UpdateHeight(p);RightBalance(p);}elsep=p-rch;returnr;}StatusAVLDelete(PAVL&p,intelem){Statusstatus=SUCCESS;if(NULL==p)returnNOT_FOUND;if(elemp-data){status=AVLDelete(p-rch,elem);if(status==SUCCESS){UpdateHeight(p);LeftBalance(p);}}elseif(elemp-data){status=AVLDelete(p-lch,elem);if(status==SUCCESS){UpdateHeight(p);RightBalance(p);}}else//找到待删除元素{if(p-lch!=NULL&&p-rch!=NULL){PAVLsucc=FindSuccession(p-rch);//寻找后继结点PAVLtmp=p;succ-lch=p-lch;succ-rch=p-rch;p=succ;//移动后继结点到当前结点UpdateHeight(p);deletetmp;}else{if(p-lch!=NULL)p=p-lch;elsep=p-rch;}LeftBalance(p);}returnstatus;}StatusAVLFind(PAVLT,intelem,int&depth){depth=1;while(T!=NULL){if(elemT-data)T=T-rch;elseif(elemT-data)T=T-lch;elsereturnSUCCESS;depth++;}returnNOT_FOUND;}intMsg(){intr;cout*****************************endl;cout*1.插入元素*endl;cout*2.删除元素*endl;cout*3.查找元素*endl;cout*0.退出程序*endl;cout*****************************endl;cout请选择：;cinr;returnr;}voidprint_proc(PAVLT,int&now,intdepth,intm[][100]){if(NULL==T)return;print_proc(T-rch,now,depth+1,m);m[now++][depth]=T-data;print_proc(T-lch,now,depth+1,m);}voidprint_avl(PAVLT){intm[100][100],num=0;memset(m,0xFF,sizeof(m));print_proc(T,num,0,m);for(inti=0;;i++){intlev_num=0;for(intj=0;jnum;j++)if(m[i][j]!=-1){lev_num++;printf(%3d,m[i][j]);}elseprintf();printf(\n);if(lev_num==0)break;}}voidcmd_insert(PAVL&T){intd;cout输入待插入的元素值：;cind;if(AVLInsert(T,d)==ERROR)cout插入元素失败!endl;else{cout插入元素成功!endl;print_avl(T);}}voidcmd_delete(PAVL&T){intd,status;cout输入待删除的元素值：;cind;status=AVLDelete(T,d);switch(status){caseSUCCESS:cout删除元素成功!endl;print_avl(T);break;caseNOT_FOUND:cout没有找到输入的元素endl;break;caseERROR:cout删除元素失败!endl;break;}}voidcmd_find(PAVL&T){intd,status,depth;cout输入待查找的元素值：;cind;status=AVLFind(T,d,depth);switch(status){caseSUCCESS:cout在深度depth找到该元素！endl;break;caseNOT_FOUND:cout没有找到输入的元素endl;break;caseERROR:cout查找元素失败!endl;break;}}intmain(){intcmd;PAVLavl=NULL;while((cmd=Msg())){switch(cmd){case1:cmd_insert(avl);break;case2:cmd_delete(avl);break;case3:cmd_find(avl);break;default:cout指令错误!endl;break;}}return0;}测试结果