实现平衡二叉树C语言

以下是C语言实现平衡二叉树的代码示例：

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

// 定义平衡二叉树结点
typedef struct AVLNode {
    int data; // 数据
    int height; // 结点高度
    struct AVLNode *left; // 左子树
    struct AVLNode *right; // 右子树
} AVLNode;

// 获取结点高度
int getHeight(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取平衡因子
int getBalanceFactor(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 更新结点高度
void updateHeight(AVLNode *node) {
    if (node == NULL) {
        return;    }
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// LL旋转
AVLNode *LLRotate(AVLNode *node) {
    AVLNode *leftChild = node->left;
    node->left = leftChild->right;
    leftChild->right = node;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

// RR旋转
AVLNode *RRRotate(AVLNode *node) {
    AVLNode *rightChild = node->right;
    node->right = rightChild->left;
    rightChild->left = node;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

// LR旋转
AVLNode *LRRotate(AVLNode *node) {
    node->left = RRRotate(node->left);
    return LLRotate(node);
}

// RL旋转
AVLNode *RLRotate(AVLNode *node) {
    node->right = LLRotate(node->right);
    return RRRotate(node);
}

// 插入结点
AVLNode *insertNode(AVLNode *node, int data) {
    if (node == NULL) {
        AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
        newNode->data = data;
        newNode->height = 1;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (data < node->data) {
        node->left = insertNode(node->left, data);
        updateHeight(node);
        if (getBalanceFactor(node) == 2) {
            if (getBalanceFactor(node->left) == 1) {
                node = LLRotate(node);
            } else {
                node = LRRotate(node);
            }
        }
    } else {
        node->right = insertNode(node->right, data);
        updateHeight(node);
        if (getBalanceFactor(node) == -2) {
            if (getBalanceFactor(node->right) == -1) {
                node = RRRotate(node);
            } else {
                node = RLRotate(node);
            }
        }
    }
    return node;
}

// 中序遍历
void inorderTraversal(AVLNode *node) {
    if (node == NULL) {
        return;
    }
    inorderTraversal(node->left);
    printf("%d ", node->data);
    inorderTraversal(node->right);
}

// 主函数
int main() {
    AVLNode *root = NULL;
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 40);
    root = insertNode(root, 50);
    root = insertNode(root, 25);
    printf("中序遍历结果：");
    inorderTraversal(root);
    return 0;
}