如何使用C语言实现平衡二叉树数据结构算法

使用C语言实现平衡二叉树数据结构算法可以分为以下几个步骤：

第一步：了解平衡二叉树

平衡二叉树是一种二叉搜索树，它具有以下特点：

• 高度平衡：每个节点的左右子树的高度差不能超过1。
• 有序性：对于任意一个节点，它的左子树中的所有节点都小于它，它的右子树中的所有节点都大于它。

平衡二叉树的优点在于它的查找、插入和删除操作都可以在O(log n)的时间内完成，比较快速。常见的平衡二叉树有红黑树和AVL树。

第二步：实现数据结构

要实现平衡二叉树，需要先定义数据结构。一个平衡二叉树节点应该包含以下信息：

• 节点值 val
• 左右子树指针 left 和 right
• 节点高度 height

定义节点结构体：

typedef struct node {
    int val;
    struct node *left;
    struct node *right;
    int height;
} Node;

然后定义插入、删除等操作。以下是AVL树的实现代码。

插入操作

首先，需要定义计算节点高度的函数：

int height(Node *node) {
    if (!node)
        return 0;
    return node->height;
}

然后，可以写出插入节点的函数。当插入一个节点时，需要更新整棵树的高度和平衡因子。若某个节点的平衡因子超过 1 或小于 -1，则可能不在平衡状态，需要进行旋转操作。

int balanceFactor(Node *node) {
    return height(node->left) - height(node->right);
}

Node* rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

Node* leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

Node* insert(Node *node, int val) {
    if (!node) {
        Node *new = (Node *)malloc(sizeof(Node));
        new->val = val;
        new->left = NULL;
        new->right = NULL;
        new->height = 1;
        return new;
    }

    if (val < node->val) {
        node->left = insert(node->left, val);
    } else if (val > node->val) {
        node->right = insert(node->right, val);
    } else {
        return node;
    }

    node->height = max(height(node->left), height(node->right)) + 1;

    int bf = balanceFactor(node);

    if (bf > 1 && val < node->left->val) {
        return rightRotate(node);
    }

    if (bf < -1 && val > node->right->val) {
        return leftRotate(node);
    }

    if (bf > 1 && val > node->left->val) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (bf < -1 && val < node->right->val) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

删除操作

删除节点时，需要在树中找到对应的节点，然后对其进行删除操作。当一个或多个节点被删除时，可能会破坏树的平衡状态，需要进行平衡操作来保证树的平衡性。

Node* minValueNode(Node *node) {
    Node *cur = node;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

Node* deleteNode(Node *node, int val) {
    if (!node) {
        return node;
    }

    if (val < node->val) {
        node->left = deleteNode(node->left, val);
    } else if (val > node->val) {
        node->right = deleteNode(node->right, val);
    } else {
        if (!node->left || !node->right) {
            Node *temp = node->left ? node->left : node->right;

            if (!temp) {
                temp = node;
                node = NULL;
            } else {
                *node = *temp;
            }

            free(temp);
        } else {
            Node *temp = minValueNode(node->right);
            node->val = temp->val;
            node->right = deleteNode(node->right, temp->val);
        }
    }

    if (!node) {
        return node;
    }

    node->height = max(height(node->left), height(node->right)) + 1;

    int bf = balanceFactor(node);

    if (bf > 1 && balanceFactor(node->left) >= 0) {
        return rightRotate(node);
    }

    if (bf > 1 && balanceFactor(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (bf < -1 && balanceFactor(node->right) <= 0) {
        return leftRotate(node);
    }

    if (bf < -1 && balanceFactor(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

第三步：测试代码

为了验证实现是否正确，需要编写测试代码。以下是两个测试样例：

插入元素

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 traversal of the constructed AVL tree is: \n");
    inorder(root);

    root = deleteNode(root, 50);

    printf("\nInorder traversal of the AVL tree after deletion of 50 is: \n");
    inorder(root);

    return 0;
}

输出：

Inorder traversal of the constructed AVL tree is:
10 20 25 30 40 50
Inorder traversal of the AVL tree after deletion of 50 is:
10 20 25 30 40

删除元素

int main() {
    Node *root = NULL;

    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);

    /*
                9
               / \
              1  10
            /  \   \
           0    5   11
           /    / \
         -1    2   6
    */

    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(root);

    root = deleteNode(root, 10);

    /*
               1
              / \
             0   9
            /   / \
          -1   5   11
              / \
             2   6
    */

    printf("\nPreorder traversal after deletion of 10 \n");
    preorder(root);

    return 0;
}

输出：

Preorder traversal of the constructed AVL tree is
1 0 -1 9 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 5 2 6 9 11

到此为止，就完成了使用C语言实现平衡二叉树数据结构算法的完整攻略。