均衡二叉樹的完成實例。本站提示廣大學習愛好者：（均衡二叉樹的完成實例）文章只能為提供參考，不一定能成為您想要的結果。以下是均衡二叉樹的完成實例正文
/*
起首均衡二叉樹是一個二叉排序樹；
其根本思惟是：
在構建二叉排序樹的進程中，當每拔出一個節點時，
先檢討能否由於拔出而損壞了樹的均衡性，若是，
找出最小不屈衡樹，停止順應的扭轉，使之成為新的均衡二叉樹。
*/
#include<cstdio>
#include<cstdlib>
#define LH 1
#define EH 0
#define RH -1
using namespace std;
typedef struct BTNode
{
int data;
int BF;//均衡因子（balance factor）
struct BTNode *lchild,*rchild;
}BTNode,*BTree;
void R_Rotate(BTree *p)//以p為根節點的二叉排序樹停止右扭轉
{
BTree L;
L=(*p)->lchild;
(*p)->lchild=L->rchild;
L->rchild=(*p);
*p=L;//p指向新的根節點
}
void L_Rotate(BTree *p)//以p為根節點的二叉排序樹停止左扭轉
{
BTree R;
R=(*p)->rchild;
(*p)->rchild=R->lchild;
R->lchild=(*p);
*p=R;
}
void LeftBalance(BTree *T)
{
BTree L,Lr;
L=(*T)->lchild;
switch(L->BF)
{
//檢討T的左子樹均衡度，並作響應的均衡處置
case LH://新節點拔出在T的左孩子的左子樹上，做單右旋處置
(*T)->BF=L->BF=EH;
R_Rotate(T);
break;
case RH://新拔出節點在T的左孩子的右子樹上，做雙旋處置
Lr=L->rchild;
switch(Lr->BF)
{
case LH:
(*T)->BF=RH;
L->BF=EH;
break;
case EH:
(*T)->BF=L->BF=EH;
break;
case RH:
(*T)->BF=EH;
L->BF=LH;
break;
}
Lr->BF=EH;
L_Rotate(&(*T)->lchild);
R_Rotate(T);
}
}
void RightBalance(BTree *T)
{
BTree R,Rl;
R=(*T)->rchild;
switch(R->BF)
{
case RH://新節點插在T的右孩子的右子樹上，要做單左旋處置
(*T)->BF=R->BF=EH;
L_Rotate(T);
break;
case LH://新節點插在T的右孩子的左子樹上，要做雙旋處置
Rl=R->lchild;
switch(Rl->BF)
{
case LH:
(*T)->BF=EH;
R->BF=RH;
break;
case EH:
(*T)->BF=R->BF=EH;
break;
case RH:
(*T)->BF=LH;
R->BF=EH;
break;
}
Rl->BF=EH;
R_Rotate(&(*T)->rchild);
L_Rotate(T);
}
}
bool InsertAVL(BTree *T,int e,bool *taller)//變量taller反響T長高與否
{
if(!*T)
{
*T=(BTree)malloc(sizeof(BTNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->BF=EH;
*taller=true;
}
else
{
if(e==(*T)->data)//不拔出
{
*taller=false;
return false;
}
if(e<(*T)->data)
{
if(!InsertAVL(&(*T)->lchild,e,taller))//未拔出
return false;
if(*taller)//以拔出左子樹，且左子樹變高
{
switch((*T)->BF)
{
case LH://本來左子樹比右子樹高，須要做左均衡處置
LeftBalance(T);
*taller=false;
break;
case EH://本來閣下子樹等高，現因左子樹增高而樹增高
(*T)->BF=LH;
*taller=true;
break;
case RH://本來右子樹比左子樹高，如今閣下子樹等高
(*T)->BF=EH;
*taller=false;
break;
}
}
}
else
{
//應在T的右子樹中搜索
if(!InsertAVL(&(*T)->rchild,e,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://本來右子樹比左子樹高，如今需做右均衡處置
RightBalance(T);
*taller=false;
break;
}
}
}
}
return true;
}
bool Find(BTree T,int key)
{
if(!T)
return false;
else if(T->data==key)
return true;
else if(T->data<key)
return Find(T->rchild,key);
else
return Find(T->lchild,key);
}
void Output(BTree T)
{
if(T)
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
Output(T->lchild);
printf(",");
Output(T->rchild);
printf(")");
}
}
}
int main(int argc,char *argv[])
{
int i;
int A[]={3,2,1,4,5,6,7,10,9,8};
BTree T=NULL;
bool taller;
for(i=0;i<sizeof(A)/sizeof(int);i++)
InsertAVL(&T,A[i],&taller);
Output(T);
printf("\n");
if(Find(T,6))
printf("6 is find in the AVL tree!\n");
else
printf("6 is not find in the AVL tree!\n");
return 0;
}
