平衡二叉树(AVL)的查找、插入和删除

平衡二叉树(AVL)的查找、插入和删除

ID:37341683

大小:308.50 KB

页数:38页

时间:2019-05-22

平衡二叉树(AVL)的查找、插入和删除_第1页
平衡二叉树(AVL)的查找、插入和删除_第2页
平衡二叉树(AVL)的查找、插入和删除_第3页
平衡二叉树(AVL)的查找、插入和删除_第4页
平衡二叉树(AVL)的查找、插入和删除_第5页
资源描述:

《平衡二叉树(AVL)的查找、插入和删除》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、平衡二叉树的查找、插入和删除平衡二叉树(AVL)查找、插入和删除小组成员:陈静101070009陈丹璐101070006陈娇10107000838第页共38页平衡二叉树的查找、插入和删除目录平衡二叉树(AVL)1查找、插入和删除1问题描述2设计说明3(一)ADT3(二)算法思想5(三)数据结构12(四)程序结构与流程13运行平台及开发工具15I/O格式15算法复杂度分析18源代码18小结37问题描述利用平衡二叉树实现一个动态查找表。38第页共38页平衡二叉树的查找、插入和删除(1)实现动态查找表的三种基本功能:查找、插入和删除。(2)初始时,平衡二叉树为空树,操作界面给

2、出创建、查找、插入和删除和退出五种操作供选择。每种操作均要提示输入关键字。创建时,根据提示输入数据,以-1为输入数据的结束标志,若输入数据重复,则给出已存在相同关键字的提示,并不将其插入到二叉树中。在查找时,如果查找的关键字不存在,则显示不存在查找的关键字,若存在则显示存在要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3页共38页-3-的关键字,若没有则进行插入并输出二叉树,若有则给出已有相同关键字的提醒。删除时首先检验原二叉树中是否存在要删除的关键字,若有则进行删除后并输出二叉树,若没有则给出不存在要删除的关键字的提醒。(3)平衡二叉树的显示采用中序遍历的方

3、法输出,还可以根据输出数据是否有序验证对平衡二叉树的操作是否正确。设计说明(一)ADTADTBalancedBinaryTree{数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标志的数据元素的关键字。数据关系R:数据元素同属一个集合。基本操作P:voidR_Rotate(BSTree&p);初始条件:二叉树存在,且关键字插入到以*p为根的二叉树的左子树的左孩子上;操作结果:对以*p为根的二叉排序树作右旋处理38第页共38页平衡二叉树的查找、插入和删除voidL_Rotate(BSTree&p);初始条件:二叉树存在,且关键字插入到以*p

4、为根的二叉树的右子树的右孩子上;操作结果:对以*p为根的二叉排序树作左旋处理voidLeftBalance(BSTree&T);初始条件:二叉树存在,且关键字插入到T所指节点为根的二叉树的左子树的右孩子上;操作结果:对以指针T所指结点为根的二叉树作左平衡旋转处理voidRightBalance(BSTree&T);初始条件:二叉树存在,且关键字插入到T所指节点为根的二叉树的右子树的左孩子上;操作结果:对以指针T所指结点为根的二叉树作右平衡旋转处理boolInsertAVL(BSTree&T,inte,bool&taller);初始条件:T存在,且e与二叉树的原有关键字不

5、同;操作结果:插入结点e平且平衡化;boolSearchBST(BSTree&T,intkey);初始条件:T存在且元素key与某关键字相同;操作结果:查找元素key是否在树T中voidPrintBST(BSTreeT);初始条件:T存在操作结果:按中序遍历输出二叉树的元素voidCreatBST(BSTree&T);初始条件:T为空操作结果:创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)voidLeftBalance_div(BSTree&p,int&shorter);38第页共38页平衡二叉树的查找、插入和删除初始条件:T存在操作结果:删除结点时左平衡旋转处

6、理voidRightBalance_div(BSTree&p,int&shorter);初始条件:T存在操作结果:删除结点时右平衡旋转处理voidDelete(BSTreeq,BSTree&r,int&shorter);初始条件:T存在且节点删除成功操作结果:删除结点intDeleteAVL(BSTree&p,intx,int&shorter);初始条件:操作结果:平衡二叉树的删除操作}ADTBalancedBinaryTree(二)算法思想1、查找在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,若查找成功,则返回指向该数据元素结点的指针,否则返回空指

7、针。如果树T为空,则查找不成功,返回空指针;当树T非空时,如果根指针T所指数据元素的关键字等于key,则查找成功,返回根指针T,否则在左子树中继续查找,若还未找到,则继续在右子树中进行查找,直到找到该数据元素或树T为空为止。38第页共38页平衡二叉树的查找、插入和删除//查找元素key是否在树T中boolSearchBST(BSTree&T,intkey){if(!T)returnfalse;elseif(EQ(key,T->data))returntrue;elseif(LT(key,T->data))returnSearchBST(T

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

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

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