定义
最小不平衡子树
基本思想
构造平衡二叉树
二叉平衡树调整的四种类型
总结
完整代码
代码语言：javascript复制#include<iostream>
using namespace std;
//平衡二叉树
//定义节点结构体
typedef struct BiNode
{
int data;//数据域
int bf;//平衡因子
BiNode* lchild, *rchild;
}BiTNode,*BiTree;
//左旋就是让最小不平衡子树的根节点成为它右孩子的左孩子
//右旋就是让最小不平衡子树的根节点成为它左孩子的右孩子
//右旋----左子树太重
void R_Rotate(BiTree& oldRoot)//这里要改变二叉树的形态，需要地址传递
{
//通过右旋，新根的右孩子指向老根，其原本的右孩子要成为老根的左孩子
BiTree newRoot = oldRoot->lchild;//新根是最小不平衡子树的根节点的左孩子
//下面这一步操作来源于二叉排序树的规则：左根右
oldRoot->lchild = newRoot->rchild;//老根的左孩子指向新根的右孩子，老根的右孩子原本是新根
//新根的右孩子指向老根
newRoot->rchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左旋----右子树太重
void L_Rotate(BiTree& oldRoot)
{
//通过左旋，新根的左孩子指向老根，其原本的左孩子要成为老根的右孩子
BiTree newRoot = oldRoot->rchild;//新根是最小不平衡子树的右孩子
oldRoot->rchild = newRoot->lchild;//老根的右孩子指向新根的左孩子，老根的右孩子原本是新根
//新根的左孩子指向老根
newRoot->lchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左平衡旋转处理---LL,LR的情况处理
#define LH 1//左高
#define EH 0//等高
#define RH -1//右高
void LeftBalance(BiTree& oldRoot)//指向最小不平衡子树的根节点
{
BiTree newRoot,Lr;//newRoot指向oldRoot的左孩子，Lr是newRoot的右孩子----这里是为了判断LR的情况发生
newRoot = oldRoot->lchild;
//因为传入的oldRoot根节点的bf大于1，是最小不平衡子树的根节点
//因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断，看是LL还是LR的情况
switch (newRoot->bf)
{
case LH://LL的情况---右旋处理，处理完后，最小不平衡子树变为平衡二叉树
{
oldRoot->bf = newRoot->bf = EH;
R_Rotate(oldRoot);//传入最小不平衡子树的根节点
break;
}
case RH://LR的情况---双旋处理---先左旋后右旋
{
//下面我们要对newRoot的右孩子的平衡因子进行判断
//新节点插入在oldRoot的左孩子的右子树上，下面我们要判断，新节点插入后，左孩子的右子树的平衡因子，因为情况不同，最后节点移动情况也会有区别
Lr = newRoot->rchild;
switch (Lr->bf)
{
//如果Lr的左孩子处增加一个新节点，那么因为最后一次是右旋转，如果newRoot的lr有右孩子便会把该右孩子分配给oldRoot
//这样一来，oldRoot最后的bf就是0,反之如果没有右孩子那么oldRoot最后的bf就是-1
//同理如果有左孩子，那么会移动给newRoot，让其最后的bf值为0,如果没有,bf为-1
case LH://新节点插入后，Lr增加了一个左孩子，右孩子为空
{
//Lr新增的节点变为了左孩子，没有右孩子
newRoot->bf = EH;
oldRoot->bf = RH;
break;
}
case EH://新节点插入后，Lr的左右孩子均存在
{
newRoot->bf = oldRoot->bf = EH;
break;
}
case RH://Lr新增的节点变为了右孩子，没有左孩子
{
oldRoot->bf = EH;
newRoot->bf = LH;
break;
}
//调整完后，初始化Lr的平衡因子
Lr->bf = EH;
//先左旋，后右旋
L_Rotate(oldRoot->lchild);
R_Rotate(oldRoot);
}
}
}
}
//右平衡旋转处理------RR,RL的情况处理---平衡右子树过重的情况
void RightBalance(BiTree& oldRoot)
{
BiNode* newRoot = oldRoot->rchild;//新根是原来最小不平衡树根的右孩子
//下面要判断新增加的节点是构成RR型还是RL型---根据newRoot的bf值进行判断
switch (newRoot->bf)
{
case RH://RR型
{
//进行左旋
newRoot->bf = oldRoot->bf = EH;
L_Rotate(oldRoot);
break;
}
case LH://RL型---需要先右旋，再左旋
{
//RL指向oldRoot的右孩子newRoot的左子树
//因为如果是RL型，新的节点会添加在newRoot的左子树下面
//下面需要判断，新节点添加后，newRoot的左子树平衡因子情况，不同的情况，最后节点移动分配情况也会不同
BiNode* RL = newRoot->lchild;
switch (RL->bf)
{
//下面我们需要判断，这个新的左孩子添加后，
//一会旋转完后，这个左孩子会分配给谁，还是原地不动，如果分配给了别的节点，会不会导致别的节点的平衡因子变化
case LH://左高---newRoot左孩子为根节点的下面新添加了一个左孩子，没有右孩子
{
//口诀：左高分配给old,分配给谁，谁平衡，没分到的缺少一个左孩子，右高
oldRoot->bf = EH;
newRoot->bf = RH;
break;
}
case EH:
{
oldRoot->bf = newRoot->bf = EH;
break;
}
case RH://右高---newRoot左孩子为根节点的下面新添加了一个右孩子，没有左孩子
{
//口诀：右高分配给new,分配给谁，谁平衡，没分到的缺少一个右孩子，左高
oldRoot->bf = LH;
newRoot->bf = EH;
break;
}
RL->bf = EH;
//先右旋后左旋
R_Rotate(oldRoot->rchild);
L_Rotate(oldRoot);
}
}
}
}
//二叉平衡树的插入操作
//如果二叉平衡树中不存在与Key值相等的值，就进行插入返回true，否则返回false表示插入失败
bool InsertAVL(BiTree& Root, int key, bool& taller)
{
//找到正确位置可以进行插入操作
if (!Root)//找到空的位置，表示可以在此位置插入
{
Root = new BiNode;
Root->data = key;
Root->lchild = Root->rchild = NULL;
Root->bf = EH;//因为新插入的节点，左右子树都为空
taller = true;
}
else
{
//出现重复值
if (Root->data == key)
{
taller = false;
return false;
}
//否则继续查找
if (key < Root->data)//去左子树里面查找
{
if (!InsertAVL(Root->lchild, key, taller))//如果插入不成功---出现重复值
{
return false;
}
if (taller)//已经插入到Root的左子树中，并且左子树长高
{
switch (Root->bf)//判断原本以Root为根的节点的平衡度
{
case LH://如果原本Root的左子树就比右子树高，再在左子树下面插入一个新节点，会造成LL型或者LR型，需要做左平衡处理
{
LeftBalance(Root);
//做出平衡处理后，高度不变
taller = false;
break;
}
case EH://原本Root的左右子树等高，现在因为左子树的增高而树增高
{
Root->bf = LH;
taller = true;
break;
}
case RH://原本Root的右子树比左子树高，现在左右子树等高
{
Root->bf = EH;
taller = false;
break;
}
}
}
}
else //否则去右子树里面查找
{
if (!InsertAVL(Root->rchild, key, taller))//没插入---出现重复值
{
return false;
}
if (taller)//如果插入到Root的右子树中并且右子树长高
{
switch (Root->bf)
{
case LH://原本左子树比右子树高，现在左右子树等高，高度不变
{
Root->bf = EH;
taller = false;
break;
}
case EH://原本左右子树等高，现在右边更高
{
Root->bf = RH;
taller = true;
break;
}
case RH://原本就是右边高，现在右边更高，需要进行右平衡处理
{
taller = false;//右平衡处理后，高度不改变,Root的bf会在右平衡处理里面改变
RightBalance(Root);
break;
}
}
}
}
}
return true;
}
//打印二叉平衡树
//递归三要素：
//1.结束条件---当前节点为空
//2.递归内容---按照左根右的顺序打印二叉平衡树
//3.返回值---无返回值
void display(BiTree root)
{
//中序遍历
if (root == NULL)
return;
display(root->lchild);
cout << root->data << " ";
display(root->rchild);
}
//下面构建二叉平衡树
void creatAVL()
{
int v[10] = { 3,2,1,4,5,6,7,10,9,8 };
BiTree root = NULL;
bool taller = false;
for (int i = 0; i < 10; i )
{
InsertAVL(root, v[i], taller);
}
cout << "打印二叉平衡树：" << " ";
display(root);
cout << endl;
if (taller)
{
cout << "大树长高高,嘻嘻嘻" << endl;
}
else
{
cout << "大树没长高,呜呜呜..." << endl;
}
}
int main()
{
creatAVL();
system("pause");
return 0;
}
这里大树之所以没长高，是因为taller记录的最后一次旋转是没有改变大树高度
增加二叉平衡树查找后的完整代码：
代码语言：javascript复制#include<iostream>
using namespace std;
//平衡二叉树
//定义节点结构体
typedef struct BiNode
{
int data;//数据域
int bf;//平衡因子
BiNode* lchild, *rchild;
}BiTNode,*BiTree;
//左旋就是让最小不平衡子树的根节点成为它右孩子的左孩子
//右旋就是让最小不平衡子树的根节点成为它左孩子的右孩子
//右旋----左子树太重
void R_Rotate(BiTree& oldRoot)//这里要改变二叉树的形态，需要地址传递
{
//通过右旋，新根的右孩子指向老根，其原本的右孩子要成为老根的左孩子
BiTree newRoot = oldRoot->lchild;//新根是最小不平衡子树的根节点的左孩子
//下面这一步操作来源于二叉排序树的规则：左根右
oldRoot->lchild = newRoot->rchild;//老根的左孩子指向新根的右孩子，老根的右孩子原本是新根
//新根的右孩子指向老根
newRoot->rchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左旋----右子树太重
void L_Rotate(BiTree& oldRoot)
{
//通过左旋，新根的左孩子指向老根，其原本的左孩子要成为老根的右孩子
BiTree newRoot = oldRoot->rchild;//新根是最小不平衡子树的右孩子
oldRoot->rchild = newRoot->lchild;//老根的右孩子指向新根的左孩子，老根的右孩子原本是新根
//新根的左孩子指向老根
newRoot->lchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左平衡旋转处理---LL,LR的情况处理
#define LH 1//左高
#define EH 0//等高
#define RH -1//右高
void LeftBalance(BiTree& oldRoot)//指向最小不平衡子树的根节点
{
BiTree newRoot,Lr;//newRoot指向oldRoot的左孩子，Lr是newRoot的右孩子----这里是为了判断LR的情况发生
newRoot = oldRoot->lchild;
//因为传入的oldRoot根节点的bf大于1，是最小不平衡子树的根节点
//因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断，看是LL还是LR的情况
switch (newRoot->bf)
{
case LH://LL的情况---右旋处理，处理完后，最小不平衡子树变为平衡二叉树
{
oldRoot->bf = newRoot->bf = EH;
R_Rotate(oldRoot);//传入最小不平衡子树的根节点
break;
}
case RH://LR的情况---双旋处理---先左旋后右旋
{
//下面我们要对newRoot的右孩子的平衡因子进行判断
//新节点插入在oldRoot的左孩子的右子树上，下面我们要判断，新节点插入后，左孩子的右子树的平衡因子，因为情况不同，最后节点移动情况也会有区别
Lr = newRoot->rchild;
switch (Lr->bf)
{
//如果Lr的左孩子处增加一个新节点，那么因为最后一次是右旋转，如果newRoot的lr有右孩子便会把该右孩子分配给oldRoot
//这样一来，oldRoot最后的bf就是0,反之如果没有右孩子那么oldRoot最后的bf就是-1
//同理如果有左孩子，那么会移动给newRoot，让其最后的bf值为0,如果没有,bf为-1
case LH://新节点插入后，Lr增加了一个左孩子，右孩子为空
{
//Lr新增的节点变为了左孩子，没有右孩子
newRoot->bf = EH;
oldRoot->bf = RH;
break;
}
case EH://新节点插入后，Lr的左右孩子均存在
{
newRoot->bf = oldRoot->bf = EH;
break;
}
case RH://Lr新增的节点变为了右孩子，没有左孩子
{
oldRoot->bf = EH;
newRoot->bf = LH;
break;
}
//调整完后，初始化Lr的平衡因子
Lr->bf = EH;
//先左旋，后右旋
L_Rotate(oldRoot->lchild);
R_Rotate(oldRoot);
}
}
}
}
//右平衡旋转处理------RR,RL的情况处理---平衡右子树过重的情况
void RightBalance(BiTree& oldRoot)
{
BiNode* newRoot = oldRoot->rchild;//新根是原来最小不平衡树根的右孩子
//下面要判断新增加的节点是构成RR型还是RL型---根据newRoot的bf值进行判断
switch (newRoot->bf)
{
case RH://RR型
{
//进行左旋
newRoot->bf = oldRoot->bf = EH;
L_Rotate(oldRoot);
break;
}
case LH://RL型---需要先右旋，再左旋
{
//RL指向oldRoot的右孩子newRoot的左子树
//因为如果是RL型，新的节点会添加在newRoot的左子树下面
//下面需要判断，新节点添加后，newRoot的左子树平衡因子情况，不同的情况，最后节点移动分配情况也会不同
BiNode* RL = newRoot->lchild;
switch (RL->bf)
{
//下面我们需要判断，这个新的左孩子添加后，
//一会旋转完后，这个左孩子会分配给谁，还是原地不动，如果分配给了别的节点，会不会导致别的节点的平衡因子变化
case LH://左高---newRoot左孩子为根节点的下面新添加了一个左孩子，没有右孩子
{
//口诀：左高分配给old,分配给谁，谁平衡，没分到的缺少一个左孩子，右高
oldRoot->bf = EH;
newRoot->bf = RH;
break;
}
case EH:
{
oldRoot->bf = newRoot->bf = EH;
break;
}
case RH://右高---newRoot左孩子为根节点的下面新添加了一个右孩子，没有左孩子
{
//口诀：右高分配给new,分配给谁，谁平衡，没分到的缺少一个右孩子，左高
oldRoot->bf = LH;
newRoot->bf = EH;
break;
}
RL->bf = EH;
//先右旋后左旋
R_Rotate(oldRoot->rchild);
L_Rotate(oldRoot);
}
}
}
}
//二叉平衡树的插入操作
//如果二叉平衡树中不存在与Key值相等的值，就进行插入返回true，否则返回false表示插入失败
bool InsertAVL(BiTree& Root, int key, bool& taller)
{
//找到正确位置可以进行插入操作
if (!Root)//找到空的位置，表示可以在此位置插入
{
Root = new BiNode;
Root->data = key;
Root->lchild = Root->rchild = NULL;
Root->bf = EH;//因为新插入的节点，左右子树都为空
taller = true;
}
else
{
//出现重复值
if (Root->data == key)
{
taller = false;
return false;
}
//否则继续查找
if (key < Root->data)//去左子树里面查找
{
if (!InsertAVL(Root->lchild, key, taller))//如果插入不成功---出现重复值
{
return false;
}
if (taller)//已经插入到Root的左子树中，并且左子树长高
{
switch (Root->bf)//判断原本以Root为根的节点的平衡度
{
case LH://如果原本Root的左子树就比右子树高，再在左子树下面插入一个新节点，会造成LL型或者LR型，需要做左平衡处理
{
LeftBalance(Root);
//做出平衡处理后，高度不变
taller = false;
break;
}
case EH://原本Root的左右子树等高，现在因为左子树的增高而树增高
{
Root->bf = LH;
taller = true;
break;
}
case RH://原本Root的右子树比左子树高，现在左右子树等高
{
Root->bf = EH;
taller = false;
break;
}
}
}
}
else //否则去右子树里面查找
{
if (!InsertAVL(Root->rchild, key, taller))//没插入---出现重复值
{
return false;
}
if (taller)//如果插入到Root的右子树中并且右子树长高
{
switch (Root->bf)
{
case LH://原本左子树比右子树高，现在左右子树等高，高度不变
{
Root->bf = EH;
taller = false;
break;
}
case EH://原本左右子树等高，现在右边更高
{
Root->bf = RH;
taller = true;
break;
}
case RH://原本就是右边高，现在右边更高，需要进行右平衡处理
{
taller = false;//右平衡处理后，高度不改变,Root的bf会在右平衡处理里面改变
RightBalance(Root);
break;
}
}
}
}
}
return true;
}
//打印二叉平衡树
//递归三要素：
//1.结束条件---当前节点为空
//2.递归内容---按照左根右的顺序打印二叉平衡树
//3.返回值---无返回值
void display(BiTree root)
{
//中序遍历
if (root == NULL)
return;
display(root->lchild);
cout << root->data << " ";
display(root->rchild);
}
//二叉平衡树的查找---非递归写法
bool findNode(const BiTree root, int val, BiTree& pos)
{
BiTree ptr = root;
while (ptr)
{
if (ptr->data == val)
{
pos = ptr;
return true;
}
else if (ptr->data > val)
{
ptr = ptr->lchild;//去左子树里面查找
}
else
{
ptr = ptr->rchild;
}
}
return false;
}
//下面构建二叉平衡树
void creatAVL()
{
int v[10] = { 3,2,1,4,5,6,7,10,9,8 };
BiTree root = NULL;
bool taller = false;
for (int i = 0; i < 10; i )
{
InsertAVL(root, v[i], taller);
}
cout << "打印二叉平衡树：" << " ";
display(root);
cout << endl;
if (taller)
{
cout << "大树长高高,嘻嘻嘻" << endl;
}
else
{
cout << "大树没长高,呜呜呜..." << endl;
}
cout << "查找6关键字：" << endl;
BiTree pos = NULL;
bool ret = findNode(root, 6, pos);
if (ret)
cout << "找到了" << pos->data << "关键字" << endl;
else
cout << "没有找到" << endl;
}
int main()
{
creatAVL();
system("pause");
return 0;
}
增加二叉平衡树删除后的完整代码：
代码语言：javascript复制#include<iostream>
using namespace std;
//平衡二叉树
//定义节点结构体
typedef struct BiNode
{
int data;//数据域
int bf;//平衡因子
BiNode* lchild, *rchild;
}BiTNode,*BiTree;
//左旋就是让最小不平衡子树的根节点成为它右孩子的左孩子
//右旋就是让最小不平衡子树的根节点成为它左孩子的右孩子
//右旋----左子树太重
void R_Rotate(BiTree& oldRoot)//这里要改变二叉树的形态，需要地址传递
{
//通过右旋，新根的右孩子指向老根，其原本的右孩子要成为老根的左孩子
BiTree newRoot = oldRoot->lchild;//新根是最小不平衡子树的根节点的左孩子
//下面这一步操作来源于二叉排序树的规则：左根右
oldRoot->lchild = newRoot->rchild;//老根的左孩子指向新根的右孩子，老根的右孩子原本是新根
//新根的右孩子指向老根
newRoot->rchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左旋----右子树太重
void L_Rotate(BiTree& oldRoot)
{
//通过左旋，新根的左孩子指向老根，其原本的左孩子要成为老根的右孩子
BiTree newRoot = oldRoot->rchild;//新根是最小不平衡子树的右孩子
oldRoot->rchild = newRoot->lchild;//老根的右孩子指向新根的左孩子，老根的右孩子原本是新根
//新根的左孩子指向老根
newRoot->lchild = oldRoot;
//老根指向新的根节点
oldRoot = newRoot;
}
//左平衡旋转处理---LL,LR的情况处理
#define LH 1//左高
#define EH 0//等高
#define RH -1//右高
void LeftBalance(BiTree& oldRoot)//指向最小不平衡子树的根节点
{
BiTree newRoot,Lr;//newRoot指向oldRoot的左孩子，Lr是newRoot的右孩子----这里是为了判断LR的情况发生
newRoot = oldRoot->lchild;
//因为传入的oldRoot根节点的bf大于1，是最小不平衡子树的根节点
//因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断，看是LL还是LR的情况
switch (newRoot->bf)
{
case LH://LL的情况---右旋处理，处理完后，最小不平衡子树变为平衡二叉树
{
oldRoot->bf = newRoot->bf = EH;
R_Rotate(oldRoot);//传入最小不平衡子树的根节点
break;
}
case RH://LR的情况---双旋处理---先左旋后右旋
{
//下面我们要对newRoot的右孩子的平衡因子进行判断
//新节点插入在oldRoot的左孩子的右子树上，下面我们要判断，新节点插入后，左孩子的右子树的平衡因子，因为情况不同，最后节点移动情况也会有区别
Lr = newRoot->rchild;
switch (Lr->bf)
{
//如果Lr的左孩子处增加一个新节点，那么因为最后一次是右旋转，如果newRoot的lr有右孩子便会把该右孩子分配给oldRoot
//这样一来，oldRoot最后的bf就是0,反之如果没有右孩子那么oldRoot最后的bf就是-1
//同理如果有左孩子，那么会移动给newRoot，让其最后的bf值为0,如果没有,bf为-1
case LH://新节点插入后，Lr增加了一个左孩子，右孩子为空
{
//Lr新增的节点变为了左孩子，没有右孩子
newRoot->bf = EH;
oldRoot->bf = RH;
break;
}
case EH://新节点插入后，Lr的左右孩子均存在
{
newRoot->bf = oldRoot->bf = EH;
break;
}
case RH://Lr新增的节点变为了右孩子，没有左孩子
{
oldRoot->bf = EH;
newRoot->bf = LH;
break;
}
//调整完后，初始化Lr的平衡因子
Lr->bf = EH;
//先左旋，后右旋
L_Rotate(oldRoot->lchild);
R_Rotate(oldRoot);
}
}
}
}
//右平衡旋转处理------RR,RL的情况处理---平衡右子树过重的情况
void RightBalance(BiTree& oldRoot)
{
BiNode* newRoot = oldRoot->rchild;//新根是原来最小不平衡树根的右孩子
//下面要判断新增加的节点是构成RR型还是RL型---根据newRoot的bf值进行判断
switch (newRoot->bf)
{
case RH://RR型
{
//进行左旋
newRoot->bf = oldRoot->bf = EH;
L_Rotate(oldRoot);
break;
}
case LH://RL型---需要先右旋，再左旋
{
//RL指向oldRoot的右孩子newRoot的左子树
//因为如果是RL型，新的节点会添加在newRoot的左子树下面
//下面需要判断，新节点添加后，newRoot的左子树平衡因子情况，不同的情况，最后节点移动分配情况也会不同
BiNode* RL = newRoot->lchild;
switch (RL->bf)
{
//下面我们需要判断，这个新的左孩子添加后，
//一会旋转完后，这个左孩子会分配给谁，还是原地不动，如果分配给了别的节点，会不会导致别的节点的平衡因子变化
case LH://左高---newRoot左孩子为根节点的下面新添加了一个左孩子，没有右孩子
{
//口诀：左高分配给old,分配给谁，谁平衡，没分到的缺少一个左孩子，右高
oldRoot->bf = EH;
newRoot->bf = RH;
break;
}
case EH:
{
oldRoot->bf = newRoot->bf = EH;
break;
}
case RH://右高---newRoot左孩子为根节点的下面新添加了一个右孩子，没有左孩子
{
//口诀：右高分配给new,分配给谁，谁平衡，没分到的缺少一个右孩子，左高
oldRoot->bf = LH;
newRoot->bf = EH;
break;
}
RL->bf = EH;
//先右旋后左旋
R_Rotate(oldRoot->rchild);
L_Rotate(oldRoot);
}
}
}
}
//二叉平衡树的插入操作
//如果二叉平衡树中不存在与Key值相等的值，就进行插入返回true，否则返回false表示插入失败
bool InsertAVL(BiTree& Root, int key, bool& taller)
{
//找到正确位置可以进行插入操作
if (!Root)//找到空的位置，表示可以在此位置插入
{
Root = new BiNode;
Root->data = key;
Root->lchild = Root->rchild = NULL;
Root->bf = EH;//因为新插入的节点，左右子树都为空
taller = true;
}
else
{
//出现重复值
if (Root->data == key)
{
taller = false;
return false;
}
//否则继续查找
if (key < Root->data)//去左子树里面查找
{
if (!InsertAVL(Root->lchild, key, taller))//如果插入不成功---出现重复值
{
return false;
}
if (taller)//已经插入到Root的左子树中，并且左子树长高
{
switch (Root->bf)//判断原本以Root为根的节点的平衡度
{
case LH://如果原本Root的左子树就比右子树高，再在左子树下面插入一个新节点，会造成LL型或者LR型，需要做左平衡处理
{
LeftBalance(Root);
//做出平衡处理后，高度不变
taller = false;
break;
}
case EH://原本Root的左右子树等高，现在因为左子树的增高而树增高
{
Root->bf = LH;
taller = true;
break;
}
case RH://原本Root的右子树比左子树高，现在左右子树等高
{
Root->bf = EH;
taller = false;
break;
}
}
}
}
else //否则去右子树里面查找
{
if (!InsertAVL(Root->rchild, key, taller))//没插入---出现重复值
{
return false;
}
if (taller)//如果插入到Root的右子树中并且右子树长高
{
switch (Root->bf)
{
case LH://原本左子树比右子树高，现在左右子树等高，高度不变
{
Root->bf = EH;
taller = false;
break;
}
case EH://原本左右子树等高，现在右边更高
{
Root->bf = RH;
taller = true;
break;
}
case RH://原本就是右边高，现在右边更高，需要进行右平衡处理
{
taller = false;//右平衡处理后，高度不改变,Root的bf会在右平衡处理里面改变
RightBalance(Root);
break;
}
}
}
}
}
return true;
}
//打印二叉平衡树
//递归三要素：
//1.结束条件---当前节点为空
//2.递归内容---按照左根右的顺序打印二叉平衡树
//3.返回值---无返回值
void display(BiTree root)
{
//中序遍历
if (root == NULL)
return;
display(root->lchild);
cout << root->data << " ";
display(root->rchild);
}
//二叉平衡树的查找---非递归写法
bool findNode(const BiTree root, int val, BiTree& pos)
{
BiTree ptr = root;
while (ptr)
{
if (ptr->data == val)
{
pos = ptr;
return true;
}
else if (ptr->data > val)
{
ptr = ptr->lchild;//去左子树里面查找
}
else
{
ptr = ptr->rchild;
}
}
return false;
}
//删除节点的函数----删除时要注意是否破坏了平衡性，以及平衡因子的大小的变化
bool Delete(BiTree& node,bool &lower)
{
BiTree parent, pre;
if (node->rchild == NULL)//右子树为空，需要重接它的左子树
{
parent = node;
node = node->lchild;
free(parent);
lower = true;
}
else if (node->lchild == NULL)//左子树为空，需要重接它的右子树
{
parent = node;
node = node->rchild;
free(parent);
lower = true;
}
else//左右子树均不为空，我们选择删除顶点的前驱节点来替代要删除的节点
{
//前驱节点要去删除顶点的左子树的最下面的右孩子里面找
parent = node;
pre = parent->lchild;
while (pre->rchild)
{
parent = pre;
pre = pre->rchild;
}
node->data = pre->data;//s的data值替换为前驱值，然后把该前驱删去
//删去的时候判断该前驱有没有左子树
if (parent != node)//重接parent的右子树为pre的左子树
{
//有左子树就接，没有接空
parent->rchild = pre->rchild;
}
else//重接parent的左子树
{
//node的左子树没有右子树，所以前驱就直接是node的左孩子
parent->lchild = pre->lchild;
}
free(pre);
lower = true;
}
return true;
}
//二叉平衡树的删除操作---增加三个变量
bool deleteNode(BiTree& root,int key)
{
static bool l=false;//删除的是左节点
static bool r=false;//删除的是右节点
static bool lower=false;//lower判断是否删除了节点
if (!root)//遍历到空，也没有找到对应删除元素
{
lower = false;
return false;
}
else
{
if (key == root->data)
Delete(root,lower);
else if (key < root->data)
{
deleteNode(root->lchild, key);
l = true;
}
else
{
deleteNode(root->rchild, key);
r = true;
}
}
//判断是否有节点删除
if (lower)
{
//删除的是左节点
if (l)
{
switch (root->bf)//当前节点原本bf值
{
case LH://原本左子树高，删除后左右相等
{
root->bf = EH;
lower = true;//标志位降低
break;
}
case EH://原本左右平衡，删除左子树后，右高
{
root->bf = RH;
lower = false;//标志位没有降低
break;
}
case RH://原本右子树高，删除左子树后，要进行右平衡调整
{
RightBalance(root);
lower = false;//高度没有降低，调整维持原本高度
break;
}
}
}
else if(r)//删除的是右节点
{
switch (root->bf)//当前节点原本bf值
{
case LH://原本左子树高，删除后要进行左平衡调整
{
LeftBalance(root);
lower = false;
break;
}
case EH://原本左右平衡，删除右子树后，左高
{
root->bf = LH;
lower = false;//标志位没有降低
break;
}
case RH://原本右子树高，删除右子树后，左右平衡
{
root->bf = EH;
lower =true;
break;
}
}
}
}
}
//下面构建二叉平衡树
void creatAVL()
{
int v[10] = { 3,2,1,4,5,6,7,10,9,8 };
BiTree root = NULL;
bool taller = false;
for (int i = 0; i < 10; i )
{
InsertAVL(root, v[i], taller);
}
cout << "打印二叉平衡树：" << " ";
display(root);
cout << endl;
if (taller)
{
cout << "大树长高高,嘻嘻嘻" << endl;
}
else
{
cout << "大树没长高,呜呜呜..." << endl;
}
cout << "查找6关键字：" << endl;
BiTree pos = NULL;
bool ret = findNode(root, 6, pos);
if (ret)
cout << "找到了" << pos->data << "关键字" << endl;
else
cout << "没有找到" << endl;
cout << "删除5关键字后:" << endl;
deleteNode(root, 5);
display(root);
cout << endl;
}
int main()
{
creatAVL();
system("pause");
return 0;
}
