没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计:平衡二叉树.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 10 浏览量
2022-06-13
08:06:56
上传
评论
收藏 387KB DOC 举报
温馨提示
试读
17页
数据结构课程设计:平衡二叉树
资源推荐
资源详情
资源评论
目 录
1 课程设计的目的和内容.........................................................................1
1.1 课程设计目的......................................................................................................................1
1.2 主要内容..............................................................................................................................1
2 课程设计分析.........................................................................................2
2.1 程序的目的和要求..............................................................................................................2
2.2 程序的主要数据和功能模块.............................................................................................2
3 详细设计.................................................................................................5
3.1 程序主要功能模块的伪代码算法.....................................................................................5
3.2 程序主要流程图..................................................................................................................8
4 测试数据与测试结果.............................................................................................................9
5 程序的使用和改进...............................................................................14
5.1 用户使用说明....................................................................................................................14
5.2 程序的改进........................................................................................................................14
平衡二叉树
1 课程设计的目的和内容
1.1 课程设计目的
复习二叉树的三叉链表存储结构和遍历方法。
掌握二叉排序树的特点和生成方法。
掌握平衡二叉树四种不平衡形态的判定和旋转为平衡的方法。
1.2 主要内容
(1)输入结点数据,构造二叉树的结点,按二叉排序树的规则插入该结
点到三叉链表中;
(2)通过插入函数 InsertAVL(BSTNode* &T,int key)插入新结点到二
叉树中,并递归调用插入函数本身,直到正确插入到二叉树中,并返回上次递
归,每返回上次递归一次同时判断其平衡度 bf,找到最小不平衡树的根结点
p。
(3)判断最小不平衡树的平衡因子(bf)的值,若 bf>1, 则调用左平衡
函数 LeftBalance(),若 bf<-1,则调用右平衡函 RightBalance(),再
判断根结点 p 的左(右)孩子的平衡因子(共有 LL 型、LR 型、RR 型、RL 型
四种),然后判定得到的不平衡形态调用不同的旋转函数即可将其重新调整为
平衡二叉树;
(4)重复步骤(1)( 2)( 3),直到所有结点都插入到该平衡二叉树
中为止;
(5)输出该二叉树的前序(或者后序)序列和中序序列,手工恢复出该
二叉树,检验其是否为平衡二叉树;并验证其中序序列的有序性。
1
平衡二叉树
2 课程设计分析
2.1 程序的目的和要求
(1)本程序演示平衡二叉树的插入,以及 AVL 的前序遍历和中序遍历,并
且验证其中序遍历有序性。
(2)对平衡二叉树出现的的的 LL,LR,RL,RR 四种情况进行处理是其平衡。
(3)接着要实现平衡二叉树的插入,其中根据平衡二叉树插入的算法要
不停的把插入的元素平衡地插入,需要判断平衡并调用左右旋转函数,更新平
衡二叉树
2.2 程序的主要数据和功能模块
(1)程序主要数据
平衡二叉树左右子树的深度:ldep,rdep
平衡因子:bf= TreeDepth(ldep)- TreeDepth(rdep)
(2)程序主要功能模块
求树深函数: TreeDepth()
左(右)旋函数: L_Rotate(), R_Rotate()
左右平衡函数: LeftBalance(), RightBalance()
插入函数 : InsertAVL()
前(中)序遍历: Preorder(), Inorder()
输出二叉树函数 Output()
(3)程序主要功能模块之间的调用
插 入 函 数 InsertAVL(BSTNode* &T,int key) 要 调 用 左 平 衡 函 数
LeftBalance()和右平衡函数 RightBalance(),左右平衡函数要调
用左旋函数 R_Rotate()和右旋函数 L_Rotate()
(4)平衡二叉树不平衡形态分析
1) LL 型:
新结点 1 插在结点 3 的左孩子的左子树里。调整方法见图 2.1。图中
以结点 2 为轴心,将 结点结点 3 从结点 2 的右上方转到结点 2 的右下侧,
使结点 3 成为结点 2 的右孩子。
2
平衡二叉树
图 2.1
2)RR 型:
新结点 3 插在结点 1 的右孩子的右子树里。调整方法见图 2.2.2。图中以
结点 2 为轴心,将结点 1 从结点 2 的左上方转到结点 2 的左下侧,使结点 1
成为结点 2 的左孩子。
图 2.2
3)LR 型:
新结点 2 插在结点 3 的左孩子的右子树里。调整方法见图 2.3 。分为两步
进行:第一步以结点 2 为轴心,将结点 1 从结点 2 的左上方转到结点 2 的左
下侧,使结点 1 成为结点 2 的左孩子,结点 2 成为结点 3 的左孩子。第二步跟
LL 型一样处理 ( 应以结点 2 为轴心 ) 。
3
1
2
3
2
1
LL 型
1
2
3
2
1
3
RR 型
3
剩余16页未读,继续阅读
资源评论
oligaga
- 粉丝: 50
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功