实习六：平衡二叉树.doc

《实习六：平衡二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告题目：平衡二叉树操作的演示一．需求分析利用平衡二叉树实现一个动态查找表。实现动态查找表的三种基本功能：查找、插入和删除。测试数据:13,24,37,90,53二．详细设计#include#include#include#include#include#defineSUCCESS0#defineERROR-1#definemax(a,b)((a)>(b)?(a):(b))#defineNOT_FOUND1usingnamespacestd;typedefintSta

2、tus;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-

3、>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)-GetH

4、eight(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

5、(PAVL&p,intelem){if(p==NULL){p=newAVL;if(!p)returnERROR;p->Init(elem);returnSUCCESS;}else{if(elem>p->data){if(AVLInsert(p->rch,elem)==ERROR)returnERROR;RightBalance(p);}elseif(elemdata){if(AVLInsert(p->lch,elem)==ERROR)returnERROR;LeftBalance(p);}elsep->count++;}UpdateHeight(p);re

6、turnSUCCESS;}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(elem>p->data){status=AVLDelete(p->rch,elem);if(status==SU

7、CCESS){UpdateHeight(p);LeftBalance(p);}}elseif(elemdata){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;//移动

8、后继结点到