# AVL树及其C++实现

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

const int LH=1; //左子树比右子树高1
const int EH=0; //左右子树一样高
const int RH=-1;//右子树比左子树高1
const int MAX_NODE_NUM=20; //结点数目上限

struct AvlNode
{
int data;
int bf;
AvlNode *lchild;
AvlNode *rchild;
};

class AvlTree
{
public:
int Get_data(AvlNode *p)
{
return p->data;
}
bool Insert_Avl(AvlNode **T,int num,bool &taller);
void L_Rotate(AvlNode **T);
void R_Rotate(AvlNode **T);
void Left_Balance(AvlNode **T);
void Right_Balance(AvlNode **T);
void InOrder_Traverse(AvlNode *T);
void Level_Traverse(AvlNode *T);
void PreOrder(AvlNode * Node);
};

void AvlTree::L_Rotate(AvlNode **T)
{
AvlNode *P=(*T)->rchild;
(*T)->rchild=P->lchild;
P->lchild=*T;

if(P->bf<0)
(*T)->bf=(*T)->bf+1-P->bf;
else
(*T)->bf=(*T)->bf+1;
if((*T)->bf>0)
P->bf=P->bf+1+(*T)->bf;
else
P->bf=P->bf+1;
*T=P;
}

void AvlTree::R_Rotate(AvlNode **T)
{
AvlNode *P=(*T)->lchild;
(*T)->lchild=P->rchild;
P->rchild=*T;

if(P->bf>0)
(*T)->bf=(*T)->bf-1-P->bf;
else
(*T)->bf=(*T)->bf-1;
if((*T)->bf<0)
P->bf=P->bf-1-(*T)->bf;
else
P->bf=P->bf-1;
*T=P;

}

void   AvlTree::Left_Balance(AvlNode **T)

{

if ((*T)->rchild->bf == 1)
R_Rotate(&(*T)->rchild);
L_Rotate(T);

}
void   AvlTree::Right_Balance(AvlNode **T)

{

if ((*T)->lchild->bf == -1)
L_Rotate(&(*T)->lchild);
R_Rotate(T);

}

void  AvlTree::InOrder_Traverse(AvlNode *T) //中序遍历
{
stack<AvlNode *> s;
AvlNode *p=T;

while(p || !s.empty())
{
if(p)
{
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
s.pop();
cout<<p->data<<”  “;
p=p->rchild;
}
}
}

void  AvlTree::Level_Traverse(AvlNode *T) //层次遍历
{
queue<AvlNode *> q;
AvlNode *p=T;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
cout<<p->data<<“:  “<<p->bf<<endl;
if(p->lchild)
q.push(p->lchild);
if(p->rchild)
q.push(p->rchild);
}
}
void AvlTree::PreOrder(AvlNode * Node)//前序遍历
{
if(Node != NULL)
{
printf(“%d “, Node->data);
PreOrder(Node->lchild);
PreOrder(Node->rchild);
}
}
bool AvlTree::Insert_Avl(AvlNode **T,int data,bool &taller)
{
if(!*T)
{
*T=new AvlNode;
(*T)->data=data;
(*T)->lchild=NULL;
(*T)->rchild=NULL;
(*T)->bf=EH;
taller=true;
}
else
{
if(data==(*T)->data)
{
taller=false;
return false;
}
if(data<(*T)->data)
{
if(!Insert_Avl(&(*T)->lchild,data,taller))
return false;
if(taller)
switch((*T)->bf)
{
case LH:
cout<<“rightbalanc: “<<(*T)->data<<endl;
(*T)->bf=2;
Right_Balance(T);
taller=false;
break;
case EH:
(*T)->bf=LH;
taller=true;
break;
case RH:
(*T)->bf=EH;
taller=false;
break;
}

}
else
{
if(!Insert_Avl(&(*T)->rchild,data,taller))
return false;
if(taller)
switch((*T)->bf)
{
case LH:
(*T)->bf=EH;
taller=false;
break;
case EH:
(*T)->bf=RH;
taller=true;
break;
case RH:
cout<<“leftbalanc: “<<(*T)->data<<endl;
(*T)->bf=-2;
Left_Balance(T);
taller=false;
break;
}
}

}
return true;
}

int main()
{
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
int b[6]={3,2,1,4,5,6};
AvlTree T;
AvlNode *root=NULL;
bool taller;
for(i=0;i<10;i++)
{
T.Insert_Avl(&root,a[i],taller);

}
T.InOrder_Traverse(root);
cout<<“root: “<<root->data<<endl;
T.PreOrder(root);
T.Level_Traverse(root);
system(“pause”);
return 0;
}

原文作者：AVL树
原文地址: https://blog.csdn.net/memmorryy/article/details/21279607
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。