c语言实现平衡二叉树

在C语言中实现平衡二叉树，通常会选用自平衡二叉搜索树（如AVL树、红黑树等）。这里我们以AVL树为例，它是一种自我平衡的二叉查找树，保证任何节点的两个子树的高度差最多为1。

以下是简单的AVL树结构和插入操作的基本示例：

// AVL树结点定义
typedef struct {
    int data;        // 节点数据
    int height;      // 节点高度
    struct node* left;   // 左子节点
    struct node* right;  // 右子节点
} Node;

// 创建新节点
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL)
        return NULL;
    node->data = data;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入函数（包含旋转操作）
void insert(Node** root, int data) {
    if (*root == NULL) {
        *root = newNode(data);
        return;
    }

    if (data < (*root)->data)
        insert(&((*root)->left), data);
    else if (data > (*root)->data)
        insert(&((*root)->right), data);

    // 更新不平衡节点的高度
    (*root)->height = 1 + max(getHeight((*root)->left),
                            getHeight((*root)->right));

    // 检查并修复不平衡
    int balance = getBalance(*root);

    // 左旋
    if (balance > 1 && data < (*root)->left->data)
        rotateRight(root);
    // 右旋
    else if (balance < -1 && data > (*root)->right->data)
        rotateLeft(root);
    // 底部情况
    else if (balance > 1 && data > (*root)->left->data) {
        // 先左旋，然后右旋
        rotateLeft(&(*root)->left);
        rotateRight(root);
    }
    else if (balance < -1 && data < (*root)->right->data) {
        // 先右旋，然后左旋
        rotateRight(&(*root)->right);
        rotateLeft(root);
    }
}

这个例子展示了基本的AVL树插入操作，包括创建新节点、更新节点高度以及通过旋转保持树的平衡。实际应用中，可能还需要处理删除节点的情况，并维护其他辅助函数。