平衡二叉树的操作：查找，打印，插入，删除（插入删除为重点）
参考http://blog.csdn.net/sysu_arui/article/details/7897017
#include<stdio.h>
#include<stdlib.h>
#define LH 1
#define EH 0
#define RH -1
typedef struct BSTNode{
int data;
int bf;
struct BSTNode lchild,rchild;
}BSTNode,*BSTree;
int Search(BSTree T,int key,BSTree &p)
{
p=NULL;
if (!T) return 0;
else if(T->data==key){
p=T;
}
else if(T->data>key){
Search(T->lchild,key,p);
}
else if(T->data<key){
Search(T->rchild,key,p);
}
return 1;
}
void PrintSearch(BSTree T,int key)
{
BSTree p;
Search(T,key,p);
if(p){
printf("the data is %d\n",p->data);
printf("the balance factor is %d",p->bf);
if(p->lchild)printf("the left child's data is %d\n",p->lchild->data);
else printf("no left child\n");
if(p->rchild)printf("the right child's data is %d\n",p->rchild->data);
else printf("no right child\n");
}
else{
printf("no such key in AVLTree\n");
}
}
void InOrder(BSTree T,int d)
{
if(T){
InOrder(T->rchild,d+1);
for(int i=0;i<d;i++) printf(" ");
printf("%d\n",T->data);
InOrder(T->lchild,d+1);
}
}
void Print(BSTree T)
{
InOrder(T,0);
}
void R_Rotate(BSTree &T)
{
BSTree lc=T->lchild;
T->lchild=lc->rchild;
lc->rchild=T;
T=lc;
}
void L_Rotate(BSTree &T)
{
BSTree rc=T->rchild;
T->rchild=rc->lchild;
rc->lchild=T;
T=rc;
}
void LeftBalance(BSTree &T)
{
BSTree lc=T->lchild;
switch(lc->bf){
case LH:T->bf=lc->bf=EH;R_Rotate(T);break;
case EH:T->bf=LH;lc->bf=RH;R_Rotate(T);break;
case RH:
BSTree rd=lc->rchild;
switch(rd->bf){
case LH:lc->bf=EH;T->bf=RH;break;
case EH:lc->bf=T->bf=EH;break;
case RH:lc->bf=LH;T->bf=EH;break;
}
rd->bf=EH;
L_Rotate(T->lchild);
R_Rotate(T);
}
}
void RightBalance(BSTree &T)
{
BSTree rc=T->rchild;
switch(rc->bf){
case RH:T->bf=rc->bf=EH;L_Rotate(T);break;
case EH:T->bf=RH;rc->bf=LH;L_Rotate(T);break;
case LH:
BSTree ld=rc->lchild;
switch(ld->bf){
case RH:T->bf=LH;rc->bf=EH;break;
case EH:T->bf=rc->bf=EH;break;
case LH:rc->bf=RH;T->bf=EH;break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
int InsertAVL(BSTree &T,int e,bool &taller)
{
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 0;
}
if(e<T->data){
if(!InsertAVL(T->lchild,e,taller)){
return 0;
}
if(taller){
switch(T->bf){
case LH:LeftBalance(T);taller=false;break;
case EH:T->bf=1;taller=true;break;
case RH:T->bf=0;taller=false;break;
}
}
}
else{
if(!InsertAVL(T->rchild,e,taller)){
return 0;
}
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 1;
}

bool deleteAVL(BSTree &t,int  key, bool& shorter)
{
    if(t == NULL)   return false; 
    else if(key==t->data)     
    {
        BSTree q = NULL;
        if(t->lchild == NULL)    
        {
            q = t;
            t = t->rchild;  
            delete q;
            shorter = true;
        }
        else if(t->rchild == NULL) 
        {
            q = t;
            t = t->lchild;
            delete q;
            shorter = true;
        }
        else                     
        {
            q = t->lchild;
            while(q->rchild)
            {
                q = q->rchild;
            }
            t->data = q->data;
            deleteAVL(t->lchild, key, shorter); 
        }
    }
    else if(key<t->data)    
    {
        if(!deleteAVL(t->lchild, key, shorter))  return false;
        if(shorter)
        {
            switch(t->bf)
            {
                case LH:  t->bf = EH;shorter = true;break;
                case EH: t->bf = RH; shorter = false;   break;
                case RH:  RightBalance(t); 
                    if(t->rchild->bf == EH) shorter = false;
                    else shorter = true;
                    break;
            }
        }
    }
    else                           
    {
        if(!deleteAVL(t->rchild, key, shorter)) return false;
        if(shorter)
        {
            switch(t->bf)
            {
                case LH:
                    LeftBalance(t);     
                    if(t->lchild->bf == EH)
                        shorter = false;
                    else
                        shorter = true;
                    break;
                case EH:
                    t->bf = LH;
                    shorter = false;
                    break;
                case RH:
                    t->bf = EH;
                    shorter = true;
                    break;
            }
        }
    }
    return true;
}
int main()
{
    bool taller=false,shorter=false;
    BSTree T=NULL;
    while(true)
    {
        int option;
        int s;
        printf(">>>>>\n");
        printf("1:Print\n2:Search\n3:Insert\n4:Delete\n5:exit\n");
        printf("<<<<<\n\n");
        scanf("%d",&option);
        switch(option){
            case 1: printf("the tree is following:\n");Print(T);break;
            case 2: printf("input the number you want to search:\n");
                    scanf("%d",&s);
                    PrintSearch(T,s);
                    break;
            case 3: printf("input the number you want to insert\n");
                    scanf("%d",&s);
                    InsertAVL(T,s,taller);
                    printf("after insert\n");
                    Print(T);
                    break;
            case 4: printf("input the number you want to delet\n");
                    scanf("%d",&s);
                    deleteAVL(T,s,shorter);
                    printf("after delete\n");
                    Print(T);
                    break;
            case 5: exit(0);
            default: printf("input is wrong,again.\n");
        }
    }
}