# 算法导论中C++实现平衡二叉树(AVL树)

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)>(b))

#define LH +1 //左高

#define EH 0 //等高

#define RH -1 //右高

#define maxSize 20

#define maxWidth 20

typedef struct BSTNode

{

int data;

int bf; //结点的平衡因子

struct BSTNode *lchild,*rchild;//左、右孩子指针

}BSTNode,*BSTree;

void R_Rotate(BSTree &p); //对以*p为根的二叉排序树作右旋处理

void L_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理

void LeftBalance(BSTree &T); //对以指针T所指结点为根的二叉树作左平衡旋转处理

void RightBalance(BSTree &T);//对以指针T所指结点为根的二叉树作右平衡旋转处理

bool InsertAVL(BSTree &T,int e,bool &taller);//插入结点e

bool SearchBST(BSTree &T,int key);//查找元素key是否在树Ｔ中

void DispTree(BSTree T);//按中序遍历输出二叉树的元素

void CreatBST(BSTree &T); //创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)

void LeftBalance_div(BSTree &p,int &shorter);//删除结点时左平衡旋转处理

void RightBalance_div(BSTree &p,int &shorter);//删除结点时右平衡旋转处理

void Delete(BSTree q,BSTree &r,int &shorter);//删除结点

int  DeleteAVL(BSTree &p,int x,int &shorter);//平衡二叉树的删除操作

int main()

{

int input,search;

bool taller=false;

int shorter=0;

BSTree T,T1,T2;

T=(BSTree)malloc(sizeof(BSTNode));

T=T1=T2=NULL;

while(1)

{

printf(“1.Create Tree\t2.Search\t3.Insert\t4.DeleteNode\t5.Exit\n”);

printf(“Choose what you want:\t”);

scanf(“%d”,&input);

getchar();

switch(input)

{

case 1:

CreatBST(T); break;

case 2:

printf(“Input the value you want to search:”);

scanf(“%d”,&search); getchar();

if(SearchBST(T,search)) printf(“Success!\n”,search);

else printf(“Faild!\n”);

break;

case 3:

printf(“Input the value you want to insert:”);

scanf(“%d”,&search); getchar();

InsertAVL(T,search,taller);

DispTree(T); break;

case 4:

printf(“Input the value you want to delete:”);

scanf(“%d”,&search); getchar();

DeleteAVL(T,search,shorter);

DispTree(T); break;

case 5:

return 1;

break;

default:printf(“Error,input again!”);break;

}

printf(“To be continue…”); getchar();

}

return 1;

}

//对以*p为根的二叉排序树作右旋处理,LL型平衡旋转法

void R_Rotate(BSTree &p)

{

BSTree lc;

lc = p->lchild; //lc指向的*p左子树根结点

p->lchild = lc->rchild; //lc的右子树挂接为*p的左子树

lc->rchild = p;

p = lc; //p指向新的结点

}

//对以*p为根的二叉排序树作左旋处理，RR型平衡旋转法

void L_Rotate(BSTree &p)

{

BSTree rc;

rc = p->rchild; //rc指向的*p右子树根结点

p->rchild = rc->lchild; //rc的左子树挂接为*p的右子树

rc->lchild = p;

p = rc; //p指向新的结点

}

//对以指针T所指结点为根的二叉树作左平衡旋转处理，LR型平衡旋转法

void LeftBalance(BSTree &T)

{

BSTree lc,rd;

lc = T->lchild; //lc指向*T的左子树根结点

switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理

{

case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理

T->bf = lc->bf = EH;

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;

L_Rotate(T->lchild); //对*T的左子树作左旋平衡处理

R_Rotate(T); //对*T作右旋平衡处理

}

}

//对以指针T所指结点为根的二叉树作右平衡旋转处理，RL型平衡旋转法

void RightBalance(BSTree &T)

{

BSTree rc,ld;

rc = T->rchild; //rc指向*T的右子树根结点

switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理

{

case RH: //新结点插入在*T的右孩子的右子树上，要作单左旋处理

T->bf = rc->bf =EH;

L_Rotate(T); break;

case LH: //新结点插入在*T的右孩子的左子树上，要作双旋处理

ld = rc->lchild; //ld指向*T的右孩子的左子树根

switch(ld->bf) //修改*T及其右孩子的平衡因子

{

case LH: T->bf = EH; rc->bf = RH; break;

case EH: T->bf = rc->bf =EH; break;

case RH: T->bf = LH; rc->bf = EH; break;

}

ld->bf = EH;

R_Rotate(T->rchild);//对*T的右子树作左旋平衡处理

L_Rotate(T); //对*T作左旋平衡处理

}

}

//插入结点e,若T中不存在和e相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0

bool InsertAVL(BSTree &T,int e,bool &taller)

{

if(!T)//插入新结点，树”长高”，置taller为true

{

T = (BSTree)malloc(sizeof(BSTNode));

T->data = e;

T->lchild = T->rchild =NULL;

T->bf = EH; taller = true;

}

else

{

if(EQ(e,T->data)) //树中已存在和有相同关键字的结点则不再插入

{

taller = false;

return 0;

}

if(LT(e,T->data)) //应继续在*T的左子树中进行搜索

{

if(!InsertAVL(T->lchild,e,taller))

return 0;//未插入

if(taller) //已插入到*T的左子树中且左子树”长高”

{

switch(T->bf) //检查*T的平衡度

{

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 0;//未插入

if(taller) //已插入到*T的右子树中且右子树”长高”

{

switch(T->bf) //检查*T的平衡度

{

case LH: //原本左子树比右子树高，现左、右子树等高

T->bf = EH; taller = false; break;

case EH: //原本左子树、右子等高，现因右子树增高而使树增高

T->bf = RH; taller = true; break;

case RH: //原本右子树比左子树高，需要作右平衡处理

RightBalance(T); taller = false; break;

}

}

}

}

return 1;

}//InsertAVL

//查找元素key是否在树Ｔ中

bool SearchBST(BSTree &T,int key)

{

if(!T) return false;

else if(EQ(key,T->data)) return true;

else if(LT(key,T->data)) return SearchBST(T->lchild,key);

else return SearchBST(T->rchild,key);

}

//层次法打印树

void DispTree(BSTree BT)

{

BSTree stack[maxSize],p;

int level[maxSize][2],top,n,i,width=4;

if(BT!=NULL)

{

printf(“Display a tree by hollow means.\n”);

top=1;

stack[top]=BT;//push root point to stack.

level[top][0]=width;

while(top>0)

{

p=stack[top];

n=level[top][0];

for(i=1;i<=n;i++)

printf(” “);

printf(“%d”,p->data);

for(i=n+1;i<maxWidth;i+=2)

printf(“–“);

printf(“\n”);

top–;

if(p->rchild!=NULL)

{

top++;

stack[top]=p->rchild;

level[top][0]=n+width;

level[top][1]=2;

}

if(p->lchild!=NULL)

{

top++;

stack[top]=p->lchild;

level[top][0]=n+width;

level[top][1]=1;

}

}

}

}

//创建平衡二叉树，（注意：以输入-1为二叉树建立的结束）

void CreatBST(BSTree &T)

{

int e;

bool taller=false;

T = NULL;

printf(“\nPlease input a key-value(end up with -1):”);

scanf(“%d”,&e);getchar();

while(e != -1)

{

InsertAVL(T,e,taller);

printf(“\nPlease input a key-value(end up with -1):”);

scanf(“%d”,&e);getchar();taller=false;

}

if(T) DispTree(T);

else printf(“Empty tree.\n”);

}

//删除结点时左平衡旋转处理

void LeftBalance_div(BSTree &p,int &shorter)

{

BSTree p1,p2;

if(p->bf==1) //p结点的左子树高，删除结点后p的bf减1,树变矮

{

p->bf=0; shorter=1;

}

else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减1,树高不变

{

p->bf=-1; shorter=0;

}

else //p结点的右子树高

{

p1=p->rchild;//p1指向p的右子树

if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变

{

L_Rotate(p);

p1->bf=1;

p->bf=-1;

shorter=0;

}

else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮

{

L_Rotate(p);

p1->bf=p->bf=0; shorter=1;

}

else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮

{

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;

}

}

}

//删除结点时右平衡旋转处理

void RightBalance_div(BSTree &p,int &shorter)

{

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)

{

R_Rotate(p);

p1->bf=-1; p->bf=1; shorter=0;

}

else if(p1->bf==1)

{

R_Rotate(p);

p1->bf=p->bf=0; 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;

}

}

}

//删除结点

void Delete(BSTree q,BSTree &r,int &shorter)

{

if(r->rchild==NULL)

{

q->data=r->data; q=r;

r=r->lchild; free(q);

shorter=1;

}

else

{

Delete(q,r->rchild,shorter);

if(shorter==1)

RightBalance_div(r,shorter);

}

}

//平衡二叉树的删除操作

int DeleteAVL(BSTree &p,int x,int &shorter)

{

int k;

BSTree q;

if(p==NULL)

{

printf(“Hava no such node !!\n”);

return 0;

}

else if(x<p->data)//在p的左子树中进行删除

{

k=DeleteAVL(p->lchild,x,shorter);

if(shorter==1)

LeftBalance_div(p,shorter);

return k;

}

else if(x>p->data)//在p的右子树中进行删除

{

k=DeleteAVL(p->rchild,x,shorter);

if(shorter==1)

RightBalance_div(p,shorter);

return k;

}

else

{

q=p;

if(p->rchild==NULL) //右子树空则只需重接它的左子树

{

p=p->lchild;

free(q);

shorter=1;

}

else if(p->lchild==NULL)//左子树空则只需重接它的右子树

{

p=p->rchild;

free(q);

shorter=1;

}

else//左右子树均不空

{

Delete(q,q->lchild,shorter);

if(shorter==1)

LeftBalance_div(p,shorter);

p=q;

}

return 1;

}

}

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