#include<stdio.h>
#include<stdlib.h>
typedef struct {
int key;
} ElemType;
typedef struct BSTNode {
ElemType data;
int bf;
struct BSTNode *lchild,*rchild;
} BSTNode,*BSTree;
//int find = 0;
//BSTree record,parent;
void R_Rotate(BSTree &p)
{
BSTree lc;
lc = p->lchild;
p->lchild = lc->rchild;
lc->rchild = p;
p=lc;
}
void L_Rotate(BSTree &p)
{
BSTree rc;
rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
#define LH 1
#define EH 0
#define RH -1
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define GT(a,b) ((a) > (b))
int SearchAVL(BSTree T,ElemType e) {
if(!T) return 0;
else if(EQ(e.key,T->data.key)) return 1;
else if(LT(e.key,T->data.key)) return SearchAVL(T->lchild,e);
else return SearchAVL(T->rchild,e);
}
void LeftBalance(BSTree &T) {
BSTree lc,rd;
lc = T->lchild;
switch(lc->bf) {
case LH:
T->bf = lc->bf = EH;
R_Rotate(T);
break;
case RH:
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);
}
}
void RightBalance(BSTree &T)
{
BSTree rc,ld;
rc = T->rchild;
switch(rc->bf) {
case RH:
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH:
ld = rc->lchild;
switch(ld->bf) {
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);
L_Rotate(T);
}
}
int InsertAVL(BSTree &T,ElemType e,int &taller)
{
if(!T) {
T = (BSTree)malloc(sizeof(BSTNode));
T->data = e;
T->lchild = T->rchild = NULL;
T->bf = EH;
taller = 1;
} else {
if(EQ(e.key,T->data.key)){
taller = 0;return 0;
}
if(LT(e.key,T->data.key)) {
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 LH:
T->bf = EH;
taller = 0;
break;
case EH:
T->bf = RH;
taller = 1;
break;
case RH:
RightBalance(T);
taller = 0;
break;
}
}
}
}
return 1;
}
BSTree FindTheLess(BSTree T)
{
//找到左子树中最大的树
BSTree temp = T->lchild;
while(1) {
if(!temp->rchild) return temp;
temp = temp->rchild;
}
}
int DelAVL(BSTree &T,ElemType e,int &lower)
{
BSTree temp;
if(!T) return 0;
if(EQ(e.key,T->data.key)) {
if(T->lchild && T->rchild) { //如果有两个子结点
temp = FindTheLess(T);
T->data = temp->data;
DelAVL(T->lchild,temp->data,lower);
} else if(T->lchild || T->rchild){ //如果只有一个子结点
temp = T;
T = T->lchild?T->lchild:T->rchild;//让原来指向要删除的结点指向该记结点的子结点
lower = 1;
free(temp);
return 1;
} else if(!T->lchild && !T->rchild) {//如果该要删除的结点是叶子,则直接删除
temp = T;
T = NULL;
lower = 1;
free(temp);
return 1;
}
} else if(LT(e.key,T->data.key)) {
if(!DelAVL(T->lchild,e,lower)) return 0;
if(lower) {
switch(T->bf) {
case EH:
T->bf = RH;
lower = 0;
break;
case LH:
T->bf = EH;
lower = 1;
break;
case RH://需要做旋转
RightBalance(T);
lower = 0;
break;
}
}
} else if(GT(e.key,T->data.key)) {
if(!DelAVL(T->rchild,e,lower)) return 0;
if(lower) {
switch(T->bf) {
case EH:
T->bf = LH;
lower = 0;
break;
case RH:
T->bf = EH;
lower = 1;
break;
case LH://需要旋转
LeftBalance(T);
lower = 0;
break;
}
}
}
return 1;
}
void MidTraverse(BSTree &T)
{
if(T) {
MidTraverse(T->lchild);
printf("%d ",T->data.key);
MidTraverse(T->rchild);
}
}
void PreTraverse(BSTree &T)
{
if(T) {
printf("%d ",T->data.key);
PreTraverse(T->lchild);
PreTraverse(T->rchild);
}
}
void Destroy(BSTree &T)
{
if(T) {
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
}
}
void print(void) {
printf("1.查找\n");
printf("2.插入\n");
printf("3.删除\n");
printf("4.退出\n");
}
int main(int argc,char *argv[])
{
int taller=0;
int lower=0;
int input;
BSTree T=NULL;
ElemType temp;
temp.key = 0;
printf("该程序演示了平衡二叉树的操作\n");
while(1) {
print();
scanf("%d",&input);
fflush(stdin);
switch(input) {
case 1:
printf("请输入要查找的数:");
scanf("%d",&temp.key);
fflush(stdin);
if(SearchAVL(T,temp)) printf("找到了\n");
else printf("找不到\n");
break;
case 2:
printf("请输入要插入的数:");
scanf("%d",&temp.key);
InsertAVL(T,temp,taller);
printf("中序遍历:");
MidTraverse(T);
printf("\n");
printf("前序遍历:");
PreTraverse(T);
printf("\n");
break;
case 3:
printf("请输入要删除的数:");
scanf("%d",&temp.key);
DelAVL(T,temp,lower);
printf("中序遍历:");
MidTraverse(T);
printf("\n");
printf("前序遍历:");
PreTraverse(T);
printf("\n");
break;
case 4:
Destroy(T);
exit(0);
}
}
return 0;
}