C语言AVL树实现（手把手教你构建自平衡二叉搜索树）

核心概念：平衡因子与旋转

平衡因子（Balance Factor） = 左子树高度 - 右子树高度。AVL树要求每个节点的平衡因子 ∈ {-1, 0, 1}。

当插入或删除节点导致某节点平衡因子超出范围时，就需要通过旋转来恢复平衡。共有四种旋转情况：

• LL（左左）：右旋
• RR（右右）：左旋
• LR（左右）：先左旋再右旋
• RL（右左）：先右旋再左旋

C语言AVL树实现步骤详解

下面我们一步步用C语言实现AVL树。首先定义节点结构：

typedef struct Node {    int data;    struct Node* left;    struct Node* right;    int height;} Node;

注意：我们额外存储了 height 字段，用于快速计算平衡因子。

辅助函数：获取高度与最大值

int max(int a, int b) {    return (a > b) ? a : b;}int getHeight(Node* node) {    if (node == NULL)        return -1; // 空节点高度为-1，叶子节点高度为0    return node->height;}

旋转函数实现

// 右旋（LL情况）Node* rotateRight(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    // 执行旋转    x->right = y;    y->left = T2;    // 更新高度    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    return x; // 新的根节点}// 左旋（RR情况）Node* rotateLeft(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    // 执行旋转    y->left = x;    x->right = T2;    // 更新高度    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    return y; // 新的根节点}

插入函数：递归插入 + 自动平衡

Node* insert(Node* node, int data) {    // 1. 执行标准BST插入    if (node == NULL) {        Node* newNode = (Node*)malloc(sizeof(Node));        newNode->data = data;        newNode->left = NULL;        newNode->right = NULL;        newNode->height = 0;        return newNode;    }    if (data < node->data)        node->left = insert(node->left, data);    else if (data > node->data)        node->right = insert(node->right, data);    else        return node; // 不允许重复值    // 2. 更新当前节点高度    node->height = 1 + max(getHeight(node->left), getHeight(node->right));    // 3. 获取平衡因子    int balance = getHeight(node->left) - getHeight(node->right);    // 4. 如果不平衡，进行旋转    // Left Left Case    if (balance > 1 && data < node->left->data)        return rotateRight(node);    // Right Right Case    if (balance < -1 && data > node->right->data)        return rotateLeft(node);    // Left Right Case    if (balance > 1 && data > node->left->data) {        node->left = rotateLeft(node->left);        return rotateRight(node);    }    // Right Left Case    if (balance < -1 && data < node->right->data) {        node->right = rotateRight(node->right);        return rotateLeft(node);    }    return node;}

完整使用示例

下面是一个简单的主函数，演示如何创建和插入数据到AVL树：

#include <stdio.h>#include <stdlib.h>// ... 上面定义的所有函数 ...void inorder(Node* root) {    if (root != NULL) {        inorder(root->left);        printf("%d ", root->data);        inorder(root->right);    }}int main() {    Node* root = NULL;    root = insert(root, 10);    root = insert(root, 20);    root = insert(root, 30); // 触发左旋    root = insert(root, 40);    root = insert(root, 50);    root = insert(root, 25); // 触发左右旋转    printf("中序遍历结果（应为有序）: ");    inorder(root);    printf("\n");    return 0;}

总结

通过本教程，你已经掌握了C语言AVL树实现的核心原理和完整代码。AVL树是学习高级数据结构的重要一步，也是面试中常见的考点。希望这份C语言数据结构教程能帮助你打下坚实基础。

记住：AVL树的关键在于自平衡二叉树代码中的旋转逻辑。多动手调试，观察不同插入顺序下的树形变化，你会对平衡机制有更深刻的理解。

现在，你可以尝试扩展功能，比如实现删除操作、查找最小/最大值、或者可视化树结构。祝你编程愉快！