通过递归建立avl树以及如何删除节点(C++版)转

    本文转自 http://www.asiteof.me/2010/06/avl/
    用到的树的节点如下所示：

struct node{
     int data;
     int bf;
     node *lchild;
     node *rchild;
};

    其中data表示该节点存储数据，bf表示当前节点的高度，lchild指向当前节点的左儿子，rchild指向当前节点的右儿子。

    对于二叉树的建立与节点的插入在本次实验中采用递归的方法，首先找到插入节点，然后递归的判断，如果节点左儿子与右儿子的高度差大于等于2，则对该节点进行平衡调整。
    对于二叉树的删除操作，先递归的搜索要删除的节点A，用该节点的右儿子的最左儿子B代替该节点，以A的右儿子和B当前的数值作为线索继续遍历，只到找到B，删除B。然后递归的对B的祖先节点进行平衡调整，具体调整操作和二叉树的插入操作的平衡调整相同。

    对二叉树的平衡调整过程，主要包含四种旋转操作：LL，LR，RR，RL。
     LR由当前节点左儿子的一次RR旋转和当前节点的一次LL旋转构成。同理， RR由当前节点右儿子的一次LL旋转和当前节点的一次RR旋转构成。

    以下为源代码：

#include <stdio .h>
#include <stdbool .h>
#include <stdlib .h>
 
char chos;
int input;
bool unbalanced = false;
struct node{
    int data;
    int bf;
    node *lchild;
    node *rchild;
};
typedef struct node *BST;
BST R = NULL;
 
void Chose(){
    printf("i) Insert a point\n"
           "d) Delete a point\n"
           "e) exit\n"
           "Input your choose:");
    scanf(" %c", &chos);
}

int Height(BST T){     /*返回当前节点的高度*/
    if(T == NULL)
        return -1;
    else
        return T->bf;
}

int Max(int A, int B){
    return ((A > B) ? A:B);
}

BST SingleRotateWithRight(BST K2){          /*RR型旋转*/
    BST K1;
    K1 = K2->rchild;
    K2->rchild = K1->lchild;
    K1->lchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST SingleRotateWithLeft(BST K2){           /*LL型旋转*/
    BST K1;
    K1 = K2->lchild;
    K2->lchild = K1->rchild;
    K1->rchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST DoubleRotateWithLeft(BST K3){           /*LR = RR(K3->lchild) + LL（K3）*/
    K3->lchild = SingleRotateWithRight(K3->lchild);
    return SingleRotateWithLeft(K3);
}

BST DoubleRotateWithRight(BST K3){          /*LL = LL(K3->lchild) + RR(K3)*/
    K3->rchild = SingleRotateWithLeft(K3->rchild);
    return SingleRotateWithRight(K3);
}

void OUT(BST T){                /*树的输出递归函数*/
    if(T->lchild){
        printf("Left\t%d\t[parent:%d]\n", T->lchild->data, T->data);
        OUT(T->lchild);
    }
    if(T->rchild){
        printf("Right\t%d\t[parent:%d]\n", T->rchild->data, T->data);
        OUT(T->rchild);
    }
}

BST Rotate(BST T){              /*对于单个节点进行的AVL调整*/
    if(Height(T->lchild) - Height(T->rchild) == 2){
        if(Height(T->lchild->lchild) >= Height(T->lchild->rchild)){
            T = SingleRotateWithLeft(T);
        }
        else{
            T = DoubleRotateWithLeft(T);
        }
    }
    if(Height(T->rchild) - Height(T->lchild) ==2){
        if(Height(T->rchild->rchild) >= Height(T->rchild->lchild)){
            T = SingleRotateWithRight(T);
        }
        else{
            T = DoubleRotateWithRight(T);
        }
    }
    return T;
}

BST AVLInsert(BST T){           /*AVL数的插入操作*/
    if(T == NULL){
        T = (BST)malloc(sizeof(struct node));
        T->data = input;
        T->lchild = T->rchild = NULL;
        T->bf = 0;
    }
    else if(input < T->data){
        T->lchild = AVLInsert(T->lchild);
        if(Height(T->lchild) - Height(T->rchild) == 2){
            if(input < T->lchild->data){
                T = SingleRotateWithLeft(T);            /*LL旋转*/
            }
            else{
                T = DoubleRotateWithLeft(T);            /*LR旋转*/
            }
        }
    }
    else if(input > T->data){
        T->rchild = AVLInsert(T->rchild);
        if(Height(T->rchild) - Height(T->lchild) == 2){
            if(input > T->rchild->data){
                T = SingleRotateWithRight(T);           /*RR旋转*/
            }
            else{
                T = DoubleRotateWithRight(T);           /*RL旋转*/
            }
        }
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    return T;
}

void Output(BST T){
    if(T == NULL){
        printf("None\n");
    }
    else{
        printf("%d\troot\n", T->data);
        OUT(T);
    }
}

void Insert(){
    printf("\nInput the point your want to Insert: ");
    scanf("%d", &input);
    R = AVLInsert(R);
    Output(R);
}

BST AVLDelete(BST T, int key){
    if(T == NULL)
        return NULL;
    if(key == T->data){
        if(T->rchild == NULL){          /*如果T得右儿子为空则直接删除*/
            BST temp = T;
            T = T->lchild;
            free(temp);
        }
        else{                           /*否则找到T->rchild的最左儿子代替T*/
            BST temp = T->rchild;
            while(temp->lchild != NULL){
                temp = temp->lchild;
            }
            T->data = temp->data;
            T->rchild = AVLDelete(T->rchild, temp->data);      /*对于替代后的T及其各个子节点进行一些列调整，正到再次递归到T->rchild的最左儿子，删除它*/
            T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
        }
        return T;
    }
    else if(key < T->data){
        T->lchild = AVLDelete(T->lchild, key);
    }
    else{
        T->rchild = AVLDelete(T->rchild, key);
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    if(T->lchild != NULL){
        T->lchild = Rotate(T->lchild);
    }
    if(T->rchild != NULL){
        T->rchild = Rotate(T->rchild);
    }
    T = Rotate(T);
    return T;
}

void Delete(){
    printf("\nInput the point you want to Delete: ");
    scanf("%d", &input);
    R = AVLDelete(R, input);
    Output(R);
}

int main(){
    while(1){
        Chose();
        switch(chos){
            case 'i':
                Insert();
                break;
            case 'd':
                Delete();
                break;
            case 'e':
                exit(0);
        }
    }
    return 0;
}

    以上代码为c++实现，但经过修改，完全可以修改为java的版本。在整个实现过程当中，添加的操作稍微简单一些，在删除节点上要考虑单个树的翻转操作。删除可以考虑为添加和逆运算，但如何逆运算则需要仔细地去处理，本文在实现上有了一个参考，接下来就可以修改为java的实现版本了。

转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201109040001.html

相关文章：

• java中删除avl树节点方法
• 深入理解java快速排序的正确性
• 冒泡,选择,插入排序的简单理解和实现