![](https://csdnimg.cn/release/download_crawler_static/45714817/bg1.jpg)
— 1 —
课 程 设 计 报 告
一. 需求分析
1、建立平衡二叉树并进行创建、增加、删除、调平等操作。
2、设计一个实现平衡二叉树的程序,可进行创建、增加、删除、调平等
操作,实现动态的输入数据,实时的输出该树结构。
3、测试数据:自选数据
二. 概要设计
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点
时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性, 若是,
则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调
整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之
成为新的平衡子树。具体步骤如下:
⑴ 每当插入一个新结点, 从该结点开始向上计算各结点的平衡因
子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平
衡因子的绝对值均不超过 1,则平衡二叉树没有失去平衡,继续插入
结点;
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于 1,则找出
其中最小不平衡子树的根结点;
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系, 确定是
哪种类型的调整;
⑷ 如果是 LL 型或 RR型,只需应用扁担原理旋转一次, 在旋转过
程中,如果出现冲突,应用旋转优先原则调整冲突;如果是 LR型或
RL型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点
先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在
旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
⑸ 计算调整后的平衡二叉树中各结点的平衡因子, 检验是否因为
旋转而破坏其他结点的平衡因子,以及调整后的平衡二叉树中是否存
在平衡因子大于 1 的结点。
三. 详细设计
树的内部变量