实习六:平衡二叉树.doc

实习六:平衡二叉树.doc

ID:55768718

大小:130.50 KB

页数:19页

时间:2020-06-06

实习六:平衡二叉树.doc_第1页
实习六:平衡二叉树.doc_第2页
实习六:平衡二叉树.doc_第3页
实习六:平衡二叉树.doc_第4页
实习六:平衡二叉树.doc_第5页
资源描述:

《实习六:平衡二叉树.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、后继结点到

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。