数据结构红黑树代码C语言

下面是一个简单的红黑树实现的C语言代码示例：

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

enum Color { RED, BLACK };

struct Node {
    int data;
    enum Color color;
    struct Node *left, *right, *parent;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->color = RED;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int data);
void fixViolation(struct Node **root, struct Node *node);
void rotateLeft(struct Node **root, struct Node *node);
void rotateRight(struct Node **root, struct Node *node);

void inorder(struct Node* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

struct Node* insert(struct Node* root, int data) {
    // Perform normal BST insertion
    if (root == NULL)
        return createNode(data);

    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    else // Duplicate keys not allowed
        return root;

    // Fix the Red-Black Tree violations
    fixViolation(&root, root->right);
    fixViolation(&root, root->left);

    return root;
}

void fixViolation(struct Node **root, struct Node *node) {
    struct Node *parent = NULL;
    struct Node *grandparent = NULL;

    while ((node != *root) && (node->color != BLACK) &&
           (node->parent->color == RED)) {
        parent = node->parent;
        grandparent = parent->parent;

        if (parent == grandparent->left) {
            struct Node *uncle = grandparent->right;
            if (uncle != NULL && uncle->color == RED) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandparent;
            } else {
                if (node == parent->right) {
                    rotateLeft(root, parent);
                    node = parent;
                    parent = node->parent;
                }
                rotateRight(root, grandparent);
                int temp = parent->color;
                parent->color = grandparent->color;
                grandparent->color = temp;
                node = parent;
            }
        } else {
            struct Node *uncle = grandparent->left;
            if ((uncle != NULL) && (uncle->color == RED)) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandparent;
            } else {
                if (node == parent->left) {
                    rotateRight(root, parent);
                    node = parent;
                    parent = node->parent;
                }
                rotateLeft(root, grandparent);
                int temp = parent->color;
                parent->color = grandparent->color;
                grandparent->color = temp;
                node = parent;
            }
        }
    }
    (*root)->color = BLACK;
}

void rotateLeft(struct Node **root, struct Node *node) {
    struct Node *rightChild = node->right;
    node->right = rightChild->left;

    if (node->right != NULL)
        node->right->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 rotateRight(struct Node **root, struct Node *node) {
    struct Node *leftChild = node->left;
    node->left = leftChild->right;

    if (node->left != NULL)
        node->left->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;
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 7);
    root = insert(root, 3);
    root = insert(root, 18);
    root = insert(root, 10);
    root = insert(root, 22);
    root = insert(root, 8);
    root = insert(root, 11);
    root = insert(root, 26);

    printf("Red-Black Tree Inorder Traversal: ");
    inorder(root);

    return 0;
}

这是一个简单的红黑树实现，包含插入和修复违规操作的函数。你可以在 `main` 函数中插入不同的值来测试红黑树的功能。最后，通过中序遍历函数 `inorder` 打印出红黑树的节点顺序。