avl.cpp
来自「平衡二叉树是数据结构中一个非常重要的概念。它对二叉树的优化和提高查询效率有重要的」· C++ 代码 · 共 566 行
CPP
566 行
#include <stdlib.h>
#include <iostream.h> //cout
#include <iomanip.h> //setw
# define LH 1 //左高
# define EH 0 //等高
# define RH -1 //右高
# define TRUE 1
# define FALSE 0
int taller=0; //taller反映T长高与否
int shorter=0; //shorter反映T变矮与否
//二叉排序树的类型定义
typedef struct BSTNode
{
int data; //结点值
int bf; //结点的平衡因子
struct BSTNode * lchild, * rchild; //分别指向左右孩子的指针
}BSTNode, *BSTree; //同时声明一个BSTNode和一个指针类型的*BSTree
//树的中序遍历的递归算法,一并输出它的平衡因子和左右结点值
void MidOrder(BSTree T)
{
//中序遍历的特点是：
//当二叉树为空，则空操作；否则
//1.中序遍历左子树；
//2.访问根结点；
//3.中序遍历右子树。
if(T->lchild) MidOrder(T->lchild);
if(T->data)
{
cout<<setw(4)<<T->data<<setw(6)<<T->bf;
if (T->lchild ) cout<<setw(8)<<T->lchild->data; else cout<<setw(8)<<"--";
if (T->rchild ) cout<<setw(8)<<T->rchild->data; else cout<<setw(8)<<"--";
cout<<endl;
}
if(T->rchild) MidOrder(T->rchild);
}
//树的先序遍历的递归算法,一并输出它的平衡因子和左右结点值
void RootOrder(BSTree T)
{
//先序遍历的特点是：
//当二叉树为空，则空操作；否则
//1.访问根结点；
//2.先序遍历左子树；
//3.先序遍历右子树。
if(T->data)
{
cout<<setw(4)<<T->data<<setw(6)<<T->bf;
if (T->lchild ) cout<<setw(8)<<T->lchild->data; else cout<<setw(8)<<"--";
if (T->rchild ) cout<<setw(8)<<T->rchild->data; else cout<<setw(8)<<"--";
cout<<endl;
}
if(T->lchild) RootOrder(T->lchild);
if(T->rchild) RootOrder(T->rchild);
}
//对以p为根的二叉排序树作右旋处理，处理之p指向新的树根结点即旋转处理之前的左子树根结点
BSTree R_Rotate(BSTree p)
{
BSTNode *lc; //声明BSTNode* 临时变量
lc=p->lchild; //lc指向的*p的左子树根结点
p->lchild=lc->rchild; //lc的右子树挂接为*p的左子树
lc->rchild=p;
p=lc; //p指向新的根结点
return p; //返回新的根结点
}
//对以p为根的二叉排序树作左旋处理，处理之p指向新的树根结点即旋转处理之前的右子树根结点
BSTree L_Rotate(BSTree p)
{
BSTNode *rc; //声明BSTNode* 临时变量
rc=p->rchild; //rc指向的*p的右子树根结点
p->rchild=rc->lchild; //rc的左子树挂接为*p的右子树
rc->lchild=p;
p=rc; //p指向新的根结点
return p; //返回新的根结点
}
//对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点
BSTree LeftBalance(BSTree T)
{
BSTNode *lc,*rd;
lc=T->lchild; //lc指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树平衡度，并做相应的平衡处理
{
case LH: //新结点插入在*T的左孩子的左子树上，要做单右旋处理
T->bf=lc->bf=EH;
T=R_Rotate(T);
break;
case RH: //新结点插入在*T的左孩子的右子树上，要做双旋处理
rd=lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{
case LH:
T->bf=RH;
lc->bf=EH;
break;
case EH:
T->bf=lc->bf=EH;
break;
case RH:
T->bf=EH;
lc->bf=LH;
break;
}
rd->bf=EH;
T->lchild=L_Rotate(T->lchild); //对*T的左孩子做左旋平衡处理
T=R_Rotate(T); //对*T做右旋处理
}
return T;
}
//对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点
BSTree RightBalance(BSTree T)
{
BSTree rc,ld;
rc=T->rchild; //rc指向*T的右子树根结点
switch(rc->bf) //检查*T的右子树平衡度，并做相应的平衡处理
{
case RH: //新结点插入在*T的右孩子的右子树上，要做单右旋处理
T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH: //新结点插入在*T的右孩子的左子树上，要做双旋处理
ld=rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case LH:
T->bf=LH;
rc->bf=EH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild); //对*T的右孩子做右旋平衡处理
T=L_Rotate(T); //对*T做左旋处理
}
return T;
}
//若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个
//数据元素为e的新结点,并返回插入后所建成的平衡二叉排序树,否则返回
//NULL.若因插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量taller
//反映T长高与否
BSTree InsertAVL(BSTree T, int e)
{
BSTree p;
//插入新结点，树长高置taller为TRUE
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else
{
//树中存在和e有相同关键字的结点则不再插入
if(e==T->data)
{
taller=FALSE;
return NULL;
}
//值小于则继续在树的左子树中搜索
if(e < T->data)
{
//插入到左子树且左子树长高
p=InsertAVL(T->lchild,e);
if(p)
{
T->lchild=p;
if(taller)
{
switch(T->bf) //检查*T的平衡度
{
case LH: //原本左子树比右子树高，需要做左平衡处理
T=LeftBalance(T);
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因左子树争高而使树增高
T->bf=LH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，现在左右子树等高
T->bf=EH;
taller=FALSE;
break;
}
}
}
}
//继续在*T的右子树中搜索
else
{
//插入到右子树且使右子树长高
p=InsertAVL(T->rchild,e);
if (p)
{
T->rchild=p;
if(taller)
{
switch(T->bf) //检查*T的平衡度
{
case LH: //原本左子树比右子树高，现在左右子树等高
T->bf=EH;
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因右子树增高而使树增高
T->bf=RH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，需要做右平衡处理
T=RightBalance(T);
taller=FALSE;
break;
}
}
}
}
}
return T;
}
//删除结点时对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点
BSTree LeftBalance1(BSTree p)
{
BSTree p1,p2;
//左子树比右子树高
if(p->bf==1)
{
p->bf=0;
shorter=1;
}
else
if(p->bf==0)
{
p->bf=-1;
shorter=0;
}
else
{
p1=p->rchild;
if(p1->bf==0)
{
p->rchild = p1->lchild;
p1->lchild = p;
p1->bf = 1;
p->bf = -1;
p = p1;
shorter = 0;
}
else
if(p1->bf==-1)
{
p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->lchild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if(p2->bf==0)
{
p->bf=0;
p1->bf=0;
}
else
if(p2->bf==-1)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
//删除结点时对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点
BSTree RightBalance1(BSTree p)
{
BSTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else
if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
p->lchild = p1->rchild;
p1->rchild = p;
p1->bf=-1;
p->bf=1;
p=p1;
shorter=0;
}
else
if(p1->bf==1)
{
p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
p2=p1->rchild;
p1->rchild = p2->lchild;
p2->lchild = p1;
p->lchild = p2->rchild;
p2->rchild = p;
if(p2->bf == 0)
{
p->bf = 0;
p1->bf = 0;
}
else
if(p2->bf == 1)
{
p->bf = -1;
p1->bf = 0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
//对结点进行删除处理
BSTree Delete(BSTree q, BSTree r)
{
if(r->rchild==NULL) //根结点的右子树为空则将左子树提高并标记树变矮了
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else //继续递规搜索并删除
{
r->rchild=Delete(q,r->rchild);
}
return r;
}
//找到要删除的结点,并调用删除函数对其进行删除
BSTree DeleteAVL(BSTree p, int e)
{
BSTree q;
//抛弃空删除
if(p==NULL) return NULL;
else
if(e < p->data) //欲删除值小于当前结点值则继续在左子树中搜索
{
p->lchild = DeleteAVL(p->lchild,e);
if(shorter==1) p=LeftBalance1(p);
return p;
}
else
if(e > p->data) //欲删除值大于当前结点值则继续在右子树中搜索
{
p->rchild=DeleteAVL(p->rchild,e);
if(shorter==1) p=RightBalance1(p);
return p;
}
else //找到了
{
q=p; //将p存储到临时变量q里面
if(p->rchild==NULL) //如果p的右子树为空则将其左子树提高一层
{
p=p->lchild;
free(q);
shorter=1; //并标记树变矮了
}
else //如果p的左子树为空则将其右子树提高一层
if(p->lchild==NULL)
{
p=p->rchild;
free(q);
shorter=1;
}
else
{
//将删除后的子树后的得到的新的子树的根结点赋值给q左子树
q->lchild=Delete(q,q->lchild);
//如果树高到变矮了则要执行删除后的左平衡处理
if(shorter==1) q=LeftBalance1(q);
p=q;
}
}
return p;
}
//建立新结点
BSTree CreatNode(int nodeValue)
{
BSTree node;
node = (BSTree)malloc(sizeof(BSTree));
node->data = nodeValue;
node->bf = 0;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
//在屏幕打印菜单函数
int PrintMenu()
{
int userChose;
cout << "---------------------" << endl;
cout << "1. 创建一棵二叉平衡树" << endl;
cout << "2. 向平衡树插入新结点" << endl;
cout << "3. 从树中删除一个结点" << endl;
cout << "4. 中序遍历输出平衡树" << endl;
cout << "5. 先序遍历输出平衡树" << endl;
cout << "n. 选择其它将退出程序" << endl;
cout << "---------------------" << endl;
cout << "请选择你的操作:";
cin >> userChose;
return userChose;
}
//新建二叉树函数
BSTree BuildTree(BSTree r)
{
//如果传入根结点不为空，则树已构建过，退出函数
if (r != NULL)
{
cout << "二叉平衡树已经创建!";
return NULL;
}
//根结点为空则开始构建
cout << "请输入结点值，输入零则结束" << endl;
int nodeValue;
cin >> nodeValue;
while (nodeValue) //插入任何不为0的整数值
{
//建立新结点
BSTree node = CreatNode(nodeValue);
//如果根为空，则将此结点设置为根结点
if (r == NULL)
{
r = node;
}
//否则将此结点作为非根结点插入
else
{
r=InsertAVL(r,nodeValue);
}
//输入新值
cin >> nodeValue;
}
return r;
}
void main()
{
//定义一个空根结点
BSTree root=NULL;
int e;
//在屏幕打印菜单，让用户选择建立、遍历、插入、删除等功能
int userChoseMenu;
while (userChoseMenu = PrintMenu())
{
//根据用户不同选择作出不同处理
switch (userChoseMenu)
{
case 1 :
cout << "你选择了1，请依次输入新树的值，回车输入下一个，遇0结束输入。" << endl;
root = BuildTree(root);
break;
case 2 :
cout << "你选择了2，请输入要插入的结点值！" << endl;
cin >> e;
root = InsertAVL(root,e);
break;
case 3 :
cout << "你选择了3，请输入要删除的结点值！" << endl;
cin >> e;
root = DeleteAVL(root,e);
break;
case 4 :
cout << "你选择了4，中序遍历输出二叉平衡树。" << endl;
cout<<"----------------------------"<<endl;
cout<<" 数据 "<<"平衡因子 "<<"左子树 "<<"右子树"<<endl;
MidOrder(root);
cout<<"----------------------------"<<endl;
break;
case 5 :
cout << "你选择了5，先序遍历输出二叉平衡树。" << endl;
cout<<"----------------------------"<<endl;
cout<<" 数据 "<<"平衡因子 "<<"左子树 "<<"右子树"<<endl;
RootOrder(root);
cout<<"----------------------------"<<endl;
break;
default :
cout << "无效选择，程序将退出。" << endl;
exit(0);
break;
}
}
//程序存在已知错误，当删除以下结点是会出现异常，忽略异常后输出的结果错误
}
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?