二叉查找树【AVL树】

数据结构课：二叉树上机实验。为了保证树的平衡性，使用AVL平衡树。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty(AvlTree T);
Position Find(int x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(int x, AvlTree T);
AvlTree Delete(int x, AvlTree T);

int GetHeight(Position P);
int Max(int a, int b);
Position SingleRotateWithLeft(Position k);
Position DoubleRotateWithLeft(Position k);
Position SingleRotateWithRight(Position k);
Position DoubleRotateWithRight(Position k);

struct AvlNode {
    int e, Height;
    AvlTree Left, Right;
};

AvlTree Delete(int x, AvlTree T) {
    if(NULL == T) {
        printf("Element not found!\n");
        return NULL;
    }

    if(x < T->e) T->Left = Delete(x, T->Left);
    else if(x > T->e) T->Right = Delete(x, T->Right);
    else { // Found the element
        if(T->Left && T->Right) {
            Position tmp = FindMin(T->Right);
            T->e = tmp->e;
            T->Right = Delete(tmp->e, T->Right);
        } else { // One or zero child
            Position tmp = T;
            if(T->Left == NULL) T = T->Right; // Include zero child
            else if(T->Right == NULL) T = T->Left;
            free(tmp);
        }
    }
    if(T) T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
    return T;
}

Position FindMax(AvlTree T) {
    if(T != NULL)
        while(T->Right) T = T->Right;
    return T;
}

Position FindMin(AvlTree T) {
    if(T == NULL) return NULL;

    if(T->Left) return FindMin(T->Left);
    else return T;
}

Position Find(int x, AvlTree T) {
    if(NULL == T) {
        printf("Not found!\n");
        return NULL;
    }

    if(x < T->e) return Find(x, T->Left);
    else if(x > T->e) return Find(x, T->Right);
    else return T;
}

AvlTree MakeEmpty(AvlTree T) {
    if(NULL != T) {
        free(T->Left);
        free(T->Right);
        free(T);
    }
    return NULL;
}

int GetHeight(Position P) {
    if(NULL == P) 
        return -1;
    else 
        return P->Height;
}

int Max(int a, int b) {
    return a > b ? a : b;
}

AvlTree Insert(int x, AvlTree T) {
    if(NULL == T) {
        T = (AvlTree)malloc(sizeof(struct AvlNode));
        if(NULL == T) {
            printf("Out of space!!!");
            return NULL;
        }
        T->e = x; T->Height = 0;
        T->Left = T->Right = NULL;
    } else if(x < T->e) {
        T->Left = Insert(x, T->Left);
        if(GetHeight(T->Left) - GetHeight(T->Right) == 2)
            if(x < T->Left->e)
                T = SingleRotateWithLeft(T);
            else 
                T = DoubleRotateWithLeft(T);
    } else if(x > T->e) {
        T->Right = Insert(x, T->Right);
        if(GetHeight(T->Right) - GetHeight(T->Left) == 2)
            if(x < T->Right->e)
                T = DoubleRotateWithRight(T);
            else 
                T = SingleRotateWithRight(T);
    }
    /* Else x is in the tree already; we'll do nothing */

    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
    return T;
}

Position SingleRotateWithLeft(Position k2) {
    Position k1;

    k1 = k2->Left;
    k2->Left = k1->Right;
    k1->Right = k2;

    k2->Height = Max(GetHeight(k2->Left), GetHeight(k2->Right)) + 1;
    k1->Height = Max(GetHeight(k1->Left), k2->Height) + 1;

    return k1;
}

Position DoubleRotateWithLeft(Position k3) {
    k3->Left = SingleRotateWithRight(k3->Left);
    return SingleRotateWithLeft(k3);
}

Position SingleRotateWithRight(Position k2) {
    Position k1;

    k1 = k2->Right;
    k2->Right = k1->Left;
    k1->Left = k2;

    k2->Height = Max(GetHeight(k2->Left), GetHeight(k2->Right)) + 1;
    k1->Height = Max(GetHeight(k1->Right), k2->Height) + 1;

    return k1;
}

Position DoubleRotateWithRight(Position k3) {
    k3->Right = SingleRotateWithLeft(k3->Right);
    return SingleRotateWithRight(k3);
}

int main() {
    AvlTree Tree = NULL, tmp;
    printf("Please insert some digits, end with EOF:\n");
    int x, i;
    while(scanf("%d", &x) != EOF)
        Tree = Insert(x, Tree);
    if(Tree) printf("Max element is %d, Min element is %d\n", FindMax(Tree)->e, FindMin(Tree)->e);
    printf("Please insert some digits to be delete, end with EOF:\n");
    while(scanf("%d", &x) != EOF)
        Tree = Delete(x, Tree);
    if(Tree) printf("Max element is %d, Min element is %d\n", FindMax(Tree)->e, FindMin(Tree)->e);
    printf("Please insert some digits to be find, end with EOF:\n");
    while(scanf("%d", &x) != EOF)
        if(tmp = Find(x, Tree)) 
            printf("%d is in the tree, address is %#x\n", x, tmp);
    MakeEmpty(Tree);
    printf("AvlTree is destoryed completely!\n");
    return 0;
}

二叉查找树【AVL树】

原文：http://blog.csdn.net/chang_mu/article/details/41088121