AVL.rar_AVL树

平衡二叉树（AVL）

查找、插入和删除

目 录

平衡二叉树（AVL） ....................................................................................................................1

查找、插入和删除........................................................................................................................1

问题描述 ........................................................................................................................................2

设计说明 ........................................................................................................................................3

（一）ADT............................................................................................................................3

（二）算法思想....................................................................................................................5

（四）程序结构与流程.....................................................................................................12

运行平台及开发工具 .................................................................................................................15

I/O 格式.......................................................................................................................................15

算法复杂度分析..........................................................................................................................17

源代码 ..........................................................................................................................................18

小结 ..............................................................................................................................................37

（1）实现动态查找表的三种基本功能：查找、插入和删除。

（2）初始时，平衡二叉树为空树，操作界面给出创建、查找、插入和删除和退出五种

存在要删除的关键字的提醒。

（3）平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证

对平衡二叉树的操作是否正确。

ADT BalancedBinaryTree{

数据对象 D：D 是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可

唯一标志的数据元素的关键字。

数据关系 R：数据元素同属一个集合。

基本操作 P：

void R_Rotate(BSTree &p);

初始条件：二叉树存在，且关键字插入到以*p 为根的二叉树的左子树的左孩子上；

操作结果：对以*p 为根的二叉排序树作右旋处理

void RightBalance(BSTree &T);

初始条件：二叉树存在，且关键字插入到 T 所指节点为根的二叉树的右子树的左孩子上；

操作结果：对以指针 T 所指结点为根的二叉树作右平衡旋转处理

bool InsertAVL(BSTree &T,int e,bool &taller);

初始条件：T 存在，且 e 与二叉树的原有关键字不同；

操作结果：插入结点 e 平且平衡化；

bool SearchBST(BSTree &T,int key);

初始条件：T 存在且元素 key 与某关键字相同；

操作结果：查找元素 key 是否在树Ｔ中

void PrintBST(BSTree T);

初始条件：T 存在

操作结果：按中序遍历输出二叉树的元素

void CreatBST(BSTree &T);

初始条件：T 为空

操作结果：创建平衡二叉树,(注意:以输入-1 为二叉树建立的结束)

void LeftBalance_div(BSTree &p,int &shorter);

初始条件：T 存在

操作结果：删除结点

int DeleteAVL(BSTree &p,int x,int &shorter);

初始条件：

操作结果：平衡二叉树的删除操作

} ADT BalancedBinaryTree

在根指针 T 所指二叉排序树中递归地查找某关键字等于 key 的数据元素，若查找成功，

则返回指向该数据元素结点的指针,否则返回空指针。如果树 T 为空，则查找不成功，返回

空指针；当树 T 非空时，如果根指针 T 所指数据元素的关键字等于 key，则查找成功，返回

根指针 T，否则在左子树中继续查找，若还未找到，则继续在右子树中进行查找，直到找到

该数据元素或树 T 为空为止。

else return SearchBST(T->rchild,key);

}

（一）若 T 为空树，则插入一个数据元素为 e 的新节点作为 T 的根节点，树长高，树