算法的建立和增加没问题了，但删除有问题，请广大楼主帮忙改改！
#include <stdio.h>
# define LH 1
# define EH 0
# define RH -1
# define TRUE 1
# define FALSE 0
# define MAX 30
int taller=0;
int shorter=0;
typedef struct BSTNode
{
int data;
int bf;
struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;
BSTree R_Rotate(BSTree p)
{
BSTNode *lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;p=lc;
return p;
} /*R_Rotate*/
BSTree L_Rotate(BSTree p)
{
BSTNode *rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;p=rc;
return p;
}/*L_Rotate*/
BSTree LeftBalance(BSTree T)
{
BSTNode *lc,*rd;
lc=T->lchild;
switch(lc->bf)
{
case LH: T->bf=lc->bf=EH;
T=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;
T->rchild=L_Rotate(T->lchild);
T=R_Rotate(T);
}
return T;
}
BSTree RightBalance(BSTree T)
{
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf)
{
case RH:T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH:ld=rc->lchild;
switch(ld->bf)
{
case LH:T->bf=LH;
rc->bf=EH;
break;
case EH:T->bf=rc->bf=EH;
break;
case RH:T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild);
T=L_Rotate(T);
}
return T;
}
BSTree InsertAVL (BSTree T, int e)
{
BSTree p;
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else
{
if(e==T->data)
{
taller=FALSE;
return NULL;
}
if(e < T->data)
{
p=InsertAVL(T->lchild,e);
if(p)
{
T->lchild=p;
if(taller)
switch(T->bf)
{
case LH:
T=LeftBalance(T);
taller=FALSE;
break;
case EH:
T->bf=LH;
taller=TRUE;
break;
case RH:
T->bf=EH;
taller=FALSE;
break;
}
}
}
else
{
p=InsertAVL(T->rchild,e);
if (p)
{
T->rchild=p;
if(taller)
{
switch(T->bf)
{
case LH: T->bf=EH;
taller=FALSE;
break;
case EH: T->bf=RH;
taller=TRUE;
break;
case RH: T=RightBalance(T);
taller=FALSE;
break;
}
}
}
}
}
return T;
}
void midorder(BSTree T)
{
if(T!=NULL)
{
midorder(T->lchild);
printf("%d ",T->data);
midorder(T->rchild);
}
}
BSTree RightBalance1(BSTree p)
{
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)
{
p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=-1;
p->bf=1;
p=p1;
shorter=0;
}
else if(p1->bf==1)
{
p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=p->bf=0;
p=p1;
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;
}
}
return p;
}
BSTree LeftBalance1(BSTree p)
{
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->rchild;
if(p1->bf==0)
{
p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=1;
p->bf=-1;
p=p1;
shorter=0;
}
else if(p1->bf==-1)
{
p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=p->bf=0;
p=p1;
shorter=1;
}
else
{
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;
}
}
return p;
}
BSTree Delete(BSTree q, BSTree r)
{
if(r->rchild==NULL)
{
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else
{
Delete(q,r->rchild);
if(shorter==1)
RightBalance1(r);
}
return r;
}
BSTree DeleteAVL(BSTree p, int e)
{
int k;
BSTree q,temp;
if(p==NULL)
return NULL;
else if(e < p->data)
{
p->lchild=DeleteAVL(p->lchild,e);
if(shorter==1)
p=LeftBalance1(p);
return p;
}
else if(e < p->data)
{
p->rchild=DeleteAVL(p->rchild,e);
if(shorter==1)
p=RightBalance1(p);
return p;
}
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
{
q->lchild=Delete(q,q->lchild);
if(shorter==1)
p=LeftBalance1(p);
p=q;
}
}
return p;
}
main()
{
int i,n,a[MAX];
BSTree T,p;
T=NULL;
printf("Enter the Sum of Node:\n");
scanf("%d",&n);
printf("Enter the Node Data:\n");
for (i=0; i < n; i++)
{
scanf("%d",&a[i]);
}
for (i=0; i < n; i++)
{
T=InsertAVL (T,a[i]);
}
midorder(T);
printf("\n");
printf("Enter the num to insert, enter \"0\" to finish!!\n");
scanf("%d",&n);
while (n!=0)
{
T=InsertAVL (T, n);
scanf("%d",&n);
}
printf("\n");
midorder(T);
printf("\n");
printf("Enter the num to delete, enter \"0\" to finish!!\n");
scanf("%d",&n);
while (n != 0)
{
T=DeleteAVL (T, n);
scanf("%d",&n);
}
midorder(T);
}
