用c语言实现红黑树插入的代码

红黑树是一种自平衡二叉搜索树，它的插入操作相对比较复杂。下面是一个简单的C语言实现红黑树插入的示例代码，供你参考：

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

// 红黑树节点
typedef struct TreeNode {
    int value; // 节点值
    int color; // 颜色，0表示黑色，1表示红色
    struct TreeNode *parent; // 父节点指针
    struct TreeNode *left; // 左子节点指针
    struct TreeNode *right; // 右子节点指针
} TreeNode;

// 创建一个红黑树节点
TreeNode* createTreeNode(int value, int color, TreeNode *parent, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = value;
    node->color = color;
    node->parent = parent;
    node->left = left;
    node->right = right;
    return node;
}

// 获取节点的颜色
int getColor(TreeNode *node) {
    if (node == NULL) {
        return 0; // 空节点为黑色
    }
    else {
        return node->color;
    }
}

// 左旋操作
void leftRotate(TreeNode **root, TreeNode *node) {
    TreeNode *rightChild = node->right;
    node->right = rightChild->left;
    if (rightChild->left != NULL) {
        rightChild->left->parent = node;
    }
    rightChild->parent = node->parent;
    if (node->parent == NULL) {
        *root = rightChild;
    }
    else if (node == node->parent->left) {
        node->parent->left = rightChild;
    }
    else {
        node->parent->right = rightChild;
    }
    rightChild->left = node;
    node->parent = rightChild;
}

// 右旋操作
void rightRotate(TreeNode **root, TreeNode *node) {
    TreeNode *leftChild = node->left;
    node->left = leftChild->right;
    if (leftChild->right != NULL) {
        leftChild->right->parent = node;
    }
    leftChild->parent = node->parent;
    if (node->parent == NULL) {
        *root = leftChild;
    }
    else if (node == node->parent->left) {
        node->parent->left = leftChild;
    }
    else {
        node->parent->right = leftChild;
    }
    leftChild->right = node;
    node->parent = leftChild;
}

// 插入操作
void insert(TreeNode **root, int value) {
    // 创建一个新节点，并初始化为红色
    TreeNode *node = createTreeNode(value, 1, NULL, NULL, NULL);

    // 执行BST插入操作
    TreeNode *parent = NULL;
    TreeNode *current = *root;
    while (current != NULL) {
        parent = current;
        if (value < current->value) {
            current = current->left;
        }
        else {
            current = current->right;
        }
    }
    node->parent = parent;
    if (parent == NULL) {
        *root = node;
    }
    else if (value < parent->value) {
        parent->left = node;
    }
    else {
        parent->right = node;
    }

    // 颜色修正
    while (getColor(node->parent) == 1) {
        if (node->parent == node->parent->parent->left) {
            TreeNode *uncle = node->parent->parent->right;
            if (getColor(uncle) == 1) {
                node->parent->color = 0;
                uncle->color = 0;
                node->parent->parent->color = 1;
                node = node->parent->parent;
            }
            else {
                if (node == node->parent->right) {
                    node = node->parent;
                    leftRotate(root, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                rightRotate(root, node->parent->parent);
            }
        }
        else {
            TreeNode *uncle = node->parent->parent->left;
            if (getColor(uncle) == 1) {
                node->parent->color = 0;
                uncle->color = 0;
                node->parent->parent->color = 1;
                node = node->parent->parent;
            }
            else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rightRotate(root, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                leftRotate(root, node->parent->parent);
            }
        }
        if (node == *root) {
            break;
        }
    }
    (*root)->color = 0;
}

// 中序遍历输出红黑树
void inorderTraversal(TreeNode *node) {
    if (node == NULL) {
        return;
    }
    inorderTraversal(node->left);
    printf("%d(%d) ", node->value, node->color);
    inorderTraversal(node->right);
}

int main() {
    TreeNode *root = NULL;

    // 插入节点
    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 30);
    insert(&root, 15);
    insert(&root, 18);
    insert(&root, 25);
    insert(&root, 40);
    insert(&root, 12);
    insert(&root, 11);

    // 输出红黑树
    printf("红黑树：");
    inorderTraversal(root);

    return 0;
}

在上面的代码中，我们首先定义了一个红黑树节点结构体，包含节点值、颜色、父节点指针、左子节点指针和右子节点指针等成员。然后，我们实现了创建节点、获取节点颜色、左旋和右旋等操作函数。最后，我们实现了插入操作和输出红黑树的函数，并在main函数中进行了测试。

需要注意的是，红黑树的插入操作相对比较复杂，需要进行颜色修正等操作，代码可能比较难理解。如果有不理解的地方，可以多看一下代码，或者参考一些其他资料。