#include"iostream"
#include"cstdlib"
#define LH 1
#define EH 0
#define RH -1
using namespace std;
//我们就用书上的方法了 ,没有用三叉链表 ,顺便复习一下书上的代码
typedef struct BSTNode
{
int data;
int bf;
BSTNode *lchild;
BSTNode *rchild;
}BSTNode,*BSTree;
void R_Rotate(BSTree &);
void L_Rotate(BSTree &);
bool InsertAVL(BSTree &,int,bool &);
void Inverse_InOrder(BSTree);
void LeftBalance(BSTree &);
void RightBalance(BSTree &);
int main()
{
BSTree T=NULL;
bool taller;
int count=0;
cout<<"请输入关键字序列,以“-1”结束(int类型)"<<endl;
int num[50];
int i=0;
cin>>num[0];
while(num[i]!=-1)
{
i++;
cin>>num[i];
}
i=0;
while(num[i]!=-1)
{
taller=0;
if(InsertAVL(T,num[i],taller))
{
count++;
cout<<"插入第"<<count<<"个后,逆中序遍历如下:"<<endl;
Inverse_InOrder(T);
cout<<endl;
}
i++;
}
system("pause");
return 0;
}
void R_Rotate(BSTree &p)
{
BSTree lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;
p=lc;
}
void L_Rotate(BSTree &p)
{
BSTree rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
bool InsertAVL(BSTree & T,int e,bool & taller)
{
if(!T)
{
T=new BSTNode;
T->data=e;
T->lchild=NULL;
T->rchild=NULL;
T->bf=EH;
taller=1;
}
else
{
if(T->data==e)
{
taller=0;
return 0;
}
if(T->data>e)
{
if(!InsertAVL(T->lchild,e,taller))
return 0;
if(taller)
{
switch(T->bf)
{
case LH:
LeftBalance(T);
taller=0;
break;
case EH:
T->bf=LH;
taller=1;
break;
case RH:
T->bf=EH;
taller=0;
break;
}
}
}
else
{
if(!InsertAVL(T->rchild,e,taller))
return 0;
if(taller)
{
switch(T->bf)
{
case RH:
RightBalance(T);
taller=0;
break;
case EH:
T->bf=RH;
taller=1;
break;
case LH:
T->bf=EH;
taller=0;
break;
}
}
}
}
return 1;
}
void Inverse_InOrder(BSTree T)
{
if(T!=NULL)
{
Inverse_InOrder(T->rchild);
cout<<(T->data)<<' ';
Inverse_InOrder(T->lchild);
}
}
void LeftBalance(BSTree &T)
{
BSTree lc=T->lchild;
switch(lc->bf)
{
case LH:
T->bf=lc->bf=EH;
R_Rotate(T);
break;
case RH:
BSTree rd=lc->rchild;
switch(rd->bf)
{
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;
L_Rotate(T->lchild);
R_Rotate(T);
break;
}
}
void RightBalance(BSTree &T)
{
BSTree rc=T->rchild;
switch(rc->bf)
{
case RH:
T->bf=rc->bf=EH;
L_Rotate(T);
break;
case LH:
BSTree ld=rc->lchild;
switch(ld->bf)
{
case RH:
T->bf=LH;
rc->bf=EH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case LH:
T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
- 1
- 2
前往页