實(shí)習(xí)六：平衡二叉樹

實(shí)驗報告題目：平衡二叉樹操作的演示一．需求分析利用平衡二叉樹實(shí)現(xiàn)一個動態(tài)查找表。實(shí)現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。測試數(shù)據(jù):13,24,37,90,53詳細(xì)設(shè)計#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#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){ returnERROR; RightBalance(p); } elseif(elem<p->data) { if(AVLInsert(p->lch,elem)==ERROR) returnERROR; LeftBalance(p); } else p->count++; } UpdateHeight(p); returnSUCCESS;}PAVLFindSuccession(PAVL&p){ PAVLr=p; if(p->lch!=NULL) { r=FindSuccession(p->lch); UpdateHeight(p); RightBalance(p); } else p=p->rch; returnr;}StatusAVLDelete(PAVL&p,intelem){ Statusstatus=SUCCESS; if(NULL==p) returnNOT_FOUND; if(elem>p->data) { status=AVLDelete(p->rch,elem); if(status==SUCCESS) { UpdateHeight(p); LeftBalance(p); } } elseif(elem<p->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);//尋找后繼結(jié)點(diǎn) PAVLtmp=p; succ->lch=p->lch; succ->rch=p->rch; p=succ;//移動后繼結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn) UpdateHeight(p); deletetmp; } else { if(p->lch!=NULL) p=p->lch; else p=p->rch; } LeftBalance(p); } returnstatus;}StatusAVLFind(PAVLT,intelem,int&depth){ depth=1; while(T!=NULL) { if(elem>T->data) T=T->rch; elseif(elem<T->data) T=T->lch; else returnSUCCESS; depth++; } returnNOT_FOUND;}intMsg(){ intr; cout<<"*****************************"<<endl; cout<<"*1.插入元素*"<<endl; cout<<"*2.刪除元素*"<<endl; cout<<"*3.查找元素*"<<endl; cout<<"*0.退出程序*"<<endl; cout<<"*****************************"<<endl; cout<<"請選擇："; cin>>r; 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;j<num;j++) if(m[i][j]!=-1) { lev_num++; printf("%3d",m[i][j]); } else printf(""); printf("\n"); if(lev_num==0) break; }}voidcmd_insert(PAVL&T){ intd; cout<<"輸入待插入的元素值："; cin>>d; if(AVLInsert(T,d)==ERROR) cout<<"插入元素失敗!"<<endl; else { cout<<"插入元素成功!"<<endl; print_avl(T); }}voidcmd_delete(PAVL&T){ intd,status; cout<<"輸入待刪除的元素值："; cin>>d; 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<<"輸入待查找的元素值："; cin>>d; 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(c