C语言平衡二叉树详解（手把手教你实现AVL树）

为什么需要平衡？

普通的二叉搜索树在极端情况下（如插入有序数据）会退化成链表，导致操作效率从 O(log n) 退化到 O(n)。而 C语言数据结构中的 AVL 树通过自动调整结构，始终保持树的“矮胖”状态，从而保证高效性能。

AVL 树的核心概念

• 平衡因子（Balance Factor）：每个节点的左子树高度减去右子树高度，值只能是 -1、0 或 1。
• 旋转操作：当插入/删除导致不平衡时，通过左旋、右旋、左右旋或右左旋恢复平衡。

C语言实现 AVL 树

下面我们用 C 语言一步步实现 AVL 树的基本功能。

1. 定义节点结构

typedef struct Node {    int data;    struct Node* left;    struct Node* right;    int height; // 记录节点高度，用于计算平衡因子} Node;

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

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;}

3. 旋转操作

右旋（Right Rotation）：用于处理左子树过高的情况。

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; // 新的根节点}

左旋（Left Rotation）：用于处理右子树过高的情况。

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; // 新的根节点}

4. 插入函数（核心逻辑）

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;}

总结

通过以上步骤，我们成功用 C 语言实现了 AVL树实现的核心逻辑。虽然代码看起来有点复杂，但只要理解了旋转的四种情况和平衡因子的计算，就能掌握这一强大的 自平衡二叉搜索树 技术。

建议你动手敲一遍代码，并尝试插入不同顺序的数据，观察树的结构变化。这不仅能加深理解，还能提升你的 C语言数据结构 编程能力。

希望这篇关于 C语言平衡二叉树 的教程对你有所帮助！