- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
(数据结构课程设计平衡二叉树操作副本
课 程 设 计 报 告
需求分析
1、建立平衡二叉树并进行创建、增加、删除、调平等操作。
2、设计一个实现平衡二叉树的程序,可进行创建、增加、删除、调平等操作,实现动态的输入数据,实时的输出该树结构。
3、测试数据:自选数据
概要设计
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。具体步骤如下:
每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;
判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或RL型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
计算调整后的平衡二叉树中各结点的平衡因子,检验是否因为旋转而破坏其他结点的平衡因子,以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;if(插入元素与当前根元素相等)
{
printf(已存在相同关键字的结点\n)
}
if(插入元素小于当前根元素))
{
if(插入新结点不成功)
return 0;
if(插入成功)
switch(查看根的平衡因子)
{
case +1:
进行左平衡处理;
{
检查*T的左子树的平衡度,并作相应平衡处理
{
case +1:
令根及其左孩子的平衡因子为0;
做右平衡处理;
{
BTree lc;
lc指向的左子树根结点
rc的右子树挂接为左子树
lc的右孩子为原结点;
原结点指向新的结点
}
break;
case -1:
rd指向*T的左孩子的右子树根
switch(查看右孩子平衡因子)
{
case +1:
根的平衡因子为-1;
根左孩子的平衡因子为0;
break;
case 0:
令根和根左孩子的平衡因子为0;
break;
case -1:
根平衡因子为0;
根左孩子平衡因子为1;
break;
}
根右孩子的平衡因子为0;
对*T的左子树作左旋平衡处理
对*T作右旋平衡处理
}
break;
case 0:
令根的平衡因子为+1;
break;
case -1:
令根的平衡因子为-1;
break;
}
}
四.调试分析
在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换,使得在调试时经常没有更改内部变量的值,导致编译出错。
对于在空树情况下删除结点的考虑,是在后期的调试检验过程中发现的。在没有更改代码前,如果按此操作,程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况,但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查,发现可以直接在输出函数中加入判断而不必再其他位置判断,并且调试成功。
五.使用说明和测试结果
测试数据:
创建二叉树
增加二叉树
直接创建平衡二叉树
平衡二叉树加入新节点并调
您可能关注的文档
最近下载
- 计量器具检定校准服务投标方案(完整技术标).docx
- 弹弹堂架设你想一个游戏那么一定要对这个有认识这样才能为.pdf
- 《常温好氧水解制复合碳源》编制说明.pdf
- 2023执业药师继续教育从8个临床问题学习氯吡格雷说明书参考答案.docx
- 护士进修汇报多学科护理的协作与合作.pptx
- 哈希HACH-NPW-160H总磷-总氮水质在线分析仪 使用手册-操作说明书.pdf
- 小学英语新人教版PEP三年级上册Unit 1 Making friends Part A第1课时教学课件(2024秋).pptx
- 《铁路桥隧养护与维修》教学课件合集.pptx
- 人教版六年级上册数学第三单元《分数除法》全单元教学课件(新插图).pptx
- 趋势交易法(鹿希武)-可直接打印.doc
文档评论(0)