#include <iostream>
#include <string.h>
using namespace std;
int unbalanced = false;
struct Data{
int key;
string name;
};
struct node{
Data data;
int bf;
node *lchild,*rchild;
};
typedef node *AVL;
void LeftRotation(AVL &T,int &unbalanced);//进行LL或LR旋转
void RightRotation(AVL &T,int &unbalanced);//进行RR或RL旋转
void InsertAVL(AVL &T,int R,string name,int unbalanced);//插入操作
AVL CreateAVL ( AVL &F );//创建AVL树
void Inorder(AVL T);//中跟顺序遍历AVL树
AVL SearchAVL(int R, AVL F );//查找操作
Data Deletemin(AVL &F );//删除
void DeleteAVL( int k, AVL &F );//删除指定元素
int main()
{
AVL F;
int R,i;
string name;
CreateAVL(F);
cout<<"中跟顺序遍历"<<endl;
Inorder (F);
while(1){
cout<<"请选择要进行的操作:"<<' '<<"1.查找"<<' '<<"2.删除"<<' '<<"3.插入"<<endl;
cin>>i;
switch(i){
case 1: {
cout<<"请输入要查找的关键字"<<endl;
cin>>R;
if(SearchAVL(R, F ) != NULL)
cout<<SearchAVL(R,F) -> data.key<<' '<<SearchAVL(R,F) -> data.name<<endl;
else cout<<"要查找的元素不存在"<<endl;
break;
}
case 2:{
cout<<"请输入要删除的关键字"<<endl;
cin>>R;
DeleteAVL( R,F );
cout<<"删除后的中根顺序遍历"<<endl;
Inorder(F); cout<<endl;
break;
}
case 3:{
cout<<"请输入要插入的关键字及姓名"<<endl;
cin>>R>>name;
InsertAVL(F,R,name,unbalanced);
cout<<"插入后的中根顺序遍历"<<endl;
Inorder(F); cout<<endl;
break;
}
default: {cout<<"请正确输入1-3!"<<endl; break;}
}
}
return 0;
}
void InsertAVL(AVL &T,int R,string name,int unbalanced){ //插入
if(! T) { //如果是空树
unbalanced = true;
T = new node;
T -> data.key = R;
T -> data.name = name;
T -> lchild = T -> rchild = NULL;
T -> bf = 0;
}
else if(R < T -> data.key){ //插入左子树
InsertAVL(T -> lchild,R,name,unbalanced);
if(unbalanced)
switch (T -> bf){
case '-1':{T -> bf = 0; unbalanced = false; break;}
case '0':{T -> bf =1;break;}
case '1':{LeftRotation(T,unbalanced);break;}
}
}
else if(R > T -> data.key){ //插入右子树
InsertAVL(T -> rchild,R,name,unbalanced);
if(unbalanced)
switch(T -> bf){
case '-1':{T -> bf = 0;unbalanced = false;break;}
case '0':{T -> bf = -1;break;}
case '1':{RightRotation(T,unbalanced);break;}
}
}
}
void LeftRotation(AVL &T,int &unbalanced){
AVL gc,lc;
lc = T -> lchild;
if(lc -> lchild -> bf == 1){ //LL旋转
T -> lchild = lc -> rchild;
lc -> rchild = T;
T -> bf = 0;
T = lc;
}
else{ //LR旋转
gc = lc -> rchild ;
lc -> rchild = gc -> lchild;
gc -> lchild = lc;
T -> lchild = gc -> rchild;
gc -> rchild = T;
switch(gc -> bf){
case '1':{T -> bf = -1;lc -> bf =0;break;}
case '0':{T -> bf = lc -> bf = 0;break;}
case '-1':{T -> bf = 0;lc -> bf =1;break;}
}
T = gc;
}
T -> bf = 0;
unbalanced = false;
}
void RightRotation(AVL &T,int &unbalanced){
AVL gc,lc;
lc = T -> rchild;
if(lc -> rchild -> bf == 1){//RR旋转
T -> rchild = lc -> lchild;
lc -> lchild = T;
T -> bf = 0;
T = lc;
}
else{ //RL旋转
gc = lc -> lchild ;
lc -> lchild = gc -> rchild;
gc -> rchild = lc;
T -> rchild = gc -> lchild;
gc -> lchild = T;
switch(gc -> bf){
case '1':{T -> bf = -1;lc -> bf =0;break;}
case '0':{T -> bf = lc -> bf = 0;break;}
case '-1':{T -> bf = 0;lc -> bf =1;break;}
}
T = gc;
}
T -> bf = 0;
unbalanced = false;
}
AVL CreateAVL ( AVL &F )
{
F = NULL; /*初始时F为空*/
int R;string name;
cout<<"请输入关键字及姓名,以“0 0”结束"<<endl;
cin>>R>>name;/*读入一个记录*/
while( R ){/*假设key=0是输入结束标志*/
InsertAVL( F , R,name,unbalanced );/* 插入记录R */
cin>>R>>name; /*读入下个记录*/
}
return F;/*返回建立的二叉查找树的根*/
}
void Inorder(AVL T){ //递归中根遍历二叉树
if( T != NULL)
{
Inorder(T -> lchild);
cout<<T -> data.key<<' '<<T -> data.name<<endl;
Inorder(T -> rchild);
}
}
AVL SearchAVL(int R, AVL F )
{ AVL p = F ;
if ( p == NULL || R == p->data.key ) // 递归终止条件
return p;
if ( R < p->data.key )
return ( SearchAVL ( R, p->lchild ) ) ; // 查找左子树
else
return ( SearchAVL( R, p->rchild ) ) ; //查找右子树
}
Data Deletemin(AVL &F )
{
Data tmp ;
AVL p ;
if ( F->lchild == NULL ) {
p = F ;
tmp = F->data ;
F = F->rchild ;
delete p ;
return tmp ;
}
else
return(Deletemin( F->lchild)) ;
}
void DeleteAVL( int k, AVL &F )
{ if ( F != NULL )
if ( k < F->data.key)
DeleteAVL( k, F->lchild ) ;
else if ( k > F->data.key)
DeleteAVL( k, F->rchild );
else
if ( F->rchild == NULL )
F = F->lchild ;
else if( F->lchild == NULL )
F = F->rchild ;
else
F->data =Deletemin(F->rchild);
}