数据结构-平衡二叉树的基本操作 （C语言代码）

参考代码:

#include<stdio.h>
#include<malloc.h>

#define True 1
#define False 0
#define EH 0
#define LH 1
#define RH -1

typedef int ElemType;

typedef struct BSTNode{
    ElemType data;
    int bf;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

void LeftRotate(BSTree *p);

void RightRotate(BSTree *p);

void LeftBalance(BSTree *T);

void RightBalance(BSTree *T);

int InsertAVL(BSTree *T, ElemType key, int *taller);

int SearchKey(BSTree T, ElemType key);

void Free(BSTree *T);

int main()
{
    BSTree T = NULL;
    int n, k, key;
    int taller;
    
    scanf("%d%d", &n, &k);
    
    while(n--){
        
        scanf("%d", &key);
        InsertAVL(&T, key, &taller);
    }
    while(k--){
        
        scanf("%d", &key);
        printf("%d ", SearchKey(T, key));
    }
    printf("\n");
    Free(&T);
    return 0;
}

void LeftRotate(BSTree *p){
    
    BSTNode *t = (*p)->rchild;
    (*p)->rchild = t->lchild;
    t->lchild = *p;
    *p = t;
}

void RightRotate(BSTree *p){
    
    BSTNode *t = (*p)->lchild;
    (*p)->lchild = t->rchild;
    t->rchild = *p;
    *p = t;
}

void LeftBalance(BSTree *T){
    
    BSTNode *lc = (*T)->lchild;
    
    switch(lc->bf){
        
    case LH:{
        
        lc->bf = (*T)->bf = EH;
        RightRotate(T);
        break;
    }
    case RH:{
        
        BSTNode *lr = lc->rchild;
        
        switch(lr->bf){
            
        case EH:{
            
            lc->bf = (*T)->bf = EH;
            break;
        }
        case LH:{
            
            lc->bf = EH;
            (*T)->bf = RH;
            break;
        }
        case RH:{
            
            lc->bf = LH;
            (*T)->bf = EH;
            break;
        }
        }
        lr->bf = EH;
        LeftRotate(&(*T)->lchild);
        RightRotate(T);
    }
    }
}

void RightBalance(BSTree *T){
    
    BSTNode *rc = (*T)->rchild;
    
    switch(rc->bf){
        
    case RH:{
        
        rc->bf = (*T)->bf = EH;
        LeftRotate(T);
        break;
    }
    case LH:{
        
        BSTNode *rl = rc->lchild;
        
        switch(rl->bf){
            
        case EH:{
            
            rc->bf = (*T)->bf = EH;
            break;
        }
        case RH:{
            
            rc->bf = EH;
            (*T)->bf = LH;
            break;
        }
        case LH:{
            
            rc->bf = RH;
            (*T)->bf = EH;
            break;
        }
        }
        rl->bf = EH;
        RightRotate(&(*T)->rchild);
        LeftRotate(T);
    }
    }
}

int InsertAVL(BSTree *T, ElemType key, int *taller){
    
    if(!*T){
        
        *T = (BSTNode *)malloc(sizeof(BSTNode));
        (*T)->bf = EH;
        (*T)->data = key;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        *taller = True;
        return True;
    }
    else if(key == (*T)->data){
        
        *taller = False;
        return False;
    }
    else if(key < (*T)->data){
        
        if(InsertAVL(&(*T)->lchild, key, taller) == False){
            
            return False;
        }
        if(*taller == True){
            
            switch((*T)->bf){
                
            case EH:{
                
                (*T)->bf = LH;
                break;
            }
            case RH:{
                
                (*T)->bf = EH;
                *taller = False;
                break;
            }
            case LH:{
                
                LeftBalance(T);
                *taller = False;
                break;
            }
            }
        }
        return True;
    }
    else{
        
        if(InsertAVL(&(*T)->rchild, key, taller) == False){
            
            return False;
        }
        if(*taller == True){
            
            switch((*T)->bf){
                
            case EH:{
                
                (*T)->bf = RH;
                break;
            }
            case LH:{
                
                (*T)->bf = EH;
                *taller = False;
                break;
            }
            case RH:{
                
                RightBalance(T);
                *taller = False;
                break;
            }
            }
        }
    }
    return True;
}

int SearchKey(BSTree T, ElemType key){
    
    BSTNode *p = T;
    
    while(p){
        
        if(key == p->data) return True;
        
        else if(key < p->data) p = p->lchild;
        
        else p = p->rchild;
    }
    return False;
}

void Free(BSTree *T) {

	if (*T) {

		Free(&(*T)->lchild);
		Free(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}