用c语言实现AVL树

AVL树是一种平衡二叉树，C语言中可以通过结构体和指针来实现AVL树。下面是一个简单的AVL树实现示例，包括AVL树的创建、插入、删除和遍历操作。

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

// 定义AVL树节点结构体
struct node {
    int data;
    int height;
    struct node *left;
    struct node *right;
};

// 获取节点高度
int get_height(struct node *root) {
    if (!root) {
        return -1;
    } else {
        return root->height;
    }
}

// 获取节点平衡因子
int get_balance_factor(struct node *root) {
    if (!root) {
        return 0;
    } else {
        return get_height(root->left) - get_height(root->right);
    }
}

// 左旋转
struct node* left_rotate(struct node *root) {
    struct node *new_root;

    new_root = root->right;
    root->right = new_root->left;
    new_root->left = root;

    root->height = 1 + (get_height(root->left) > get_height(root->right) ? get_height(root->left) : get_height(root->right));
    new_root->height = 1 + (get_height(new_root->left) > get_height(new_root->right) ? get_height(new_root->left) : get_height(new_root->right));

    return new_root;
}

// 右旋转
struct node* right_rotate(struct node *root) {
    struct node *new_root;

    new_root = root->left;
    root->left = new_root->right;
    new_root->right = root;

    root->height = 1 + (get_height(root->left) > get_height(root->right) ? get_height(root->left) : get_height(root->right));
    new_root->height = 1 + (get_height(new_root->left) > get_height(new_root->right) ? get_height(new_root->left) : get_height(new_root->right));

    return new_root;
}

// 创建AVL树
struct node* create_avl_tree() {
    struct node *root;
    int data;

    printf("请输入根节点的数据：");
    scanf("%d", &data);

    root = (struct node*) malloc(sizeof(struct node));
    if (!root) {
        printf("内存分配失败\n");
        exit(1);
    }
    root->data = data;
    root->height = 0;
    root->left = NULL;
    root->right = NULL;

    return root;
}

// 插入节点
struct node* insert_node(struct node *root, int data) {
    if (!root) {
        root = (struct node*) malloc(sizeof(struct node));
        if (!root) {
            printf("内存分配失败\n");
            exit(1);
        }
        root->data = data;
        root->height = 0;
        root->left = NULL;
        root->right = NULL;
    } else if (data < root->data) {
        root->left = insert_node(root->left, data);
        if (get_balance_factor(root) == 2) {
            if (get_balance_factor(root->left) == 1) {
                root = right_rotate(root);
            } else if (get_balance_factor(root->left) == -1) {
                root->left = left_rotate(root->left);
                root = right_rotate(root);
            }
        }
    } else if (data > root->data) {
        root->right = insert_node(root->right, data);
        if (get_balance_factor(root) == -2) {
            if (get_balance_factor(root->right) == -1) {
                root = left_rotate(root);
            } else if (get_balance_factor(root->right) == 1) {
                root->right = right_rotate(root->right);
                root = left_rotate(root);
            }
        }
    } else {
        printf("节点已存在\n");
    }

    root->height = 1 + (get_height(root->left) > get_height(root->right) ? get_height(root->left) : get_height(root->right));

    return root;
}

// 删除节点
struct node* delete_node(struct node *root, int data) {
    struct node *p;

    if (!root) {
        printf("节点不存在\n");
    } else if (data < root->data) {
        root->left = delete_node(root->left, data);
        if (get_balance_factor(root) == -2) {
            if (get_balance_factor(root->right) == -1) {
                root = left_rotate(root);
            } else if (get_balance_factor(root->right) == 1) {
                root->right = right_rotate(root->right);
                root = left_rotate(root);
            }
        }
    } else if (data > root->data) {
        root->right = delete_node(root->right, data);
        if (get_balance_factor(root) == 2) {
            if (get_balance_factor(root->left) == 1) {
                root = right_rotate(root);
            } else if (get_balance