c语言红黑树代码

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

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

// 定义红黑树节点结构体
typedef struct RBNode {
    int data;
    int color;
    struct RBNode *left;
    struct RBNode *right;
    struct RBNode *parent;
} RBNode;

// 定义红黑树结构体
typedef struct RBTree {
    RBNode *root;
} RBTree;

// 定义常量
#define RED 0
#define BLACK 1

// 初始化红黑树
void init(RBTree *tree) {
    tree->root = NULL;
}

// 树的左旋操作
void leftRotate(RBTree *tree, RBNode *node) {
    RBNode *right = node->right;
    node->right = right->left;
    if (right->left != NULL) {
        right->left->parent = node;
    }
    right->parent = node->parent;
    if (node->parent == NULL) {
        tree->root = right;
    } else if (node == node->parent->left) {
        node->parent->left = right;
    } else {
        node->parent->right = right;
    }
    right->left = node;
    node->parent = right;
}

// 树的右旋操作
void rightRotate(RBTree *tree, RBNode *node) {
    RBNode *left = node->left;
    node->left = left->right;
    if (left->right != NULL) {
        left->right->parent = node;
    }
    left->parent = node->parent;
    if (node->parent == NULL) {
        tree->root = left;
    } else if (node == node->parent->right) {
        node->parent->right = left;
    } else {
        node->parent->left = left;
    }
    left->right = node;
    node->parent = left;
}

// 插入节点
void insert(RBTree *tree, int data) {
    RBNode *node = (RBNode *)malloc(sizeof(RBNode));
    node->data = data;
    node->color = RED;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    RBNode *parent = NULL;
    RBNode *current = tree->root;
    while (current != NULL) {
        parent = current;
        if (node->data < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    node->parent = parent;
    if (parent == NULL) {
        tree->root = node;
    } else if (node->data < parent->data) {
        parent->left = node;
    } else {
        parent->right = node;
    }
    while (node != tree->root && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            RBNode *uncle = node->parent->parent->right;
            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    leftRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(tree, node->parent->parent);
            }
        } else {
            RBNode *uncle = node->parent->parent->left;
            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rightRotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                leftRotate(tree, node->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

// 中序遍历
void inorder(RBNode *node) {
    if (node != NULL) {
        inorder(node->left);
        printf("%d ", node->data);
        inorder(node->right);
    }
}

int main() {
    RBTree tree;
    init(&tree);
    insert(&tree, 10);
    insert(&tree, 20);
    insert(&tree, 30);
    insert(&tree, 15);
    insert(&tree, 18);
    insert(&tree, 25);
    insert(&tree, 5);
    inorder(tree.root);
    return 0;
}

这段代码使用了结构体定义红黑树节点和红黑树，以及一些常量和函数来实现红黑树的插入和中序遍历操作。代码中的 `insert` 函数使用了红黑树的插入算法来插入新的节点，并维护红黑树的性质。在 `main` 函数中，我们插入了一些数据并进行了中序遍历操作，以验证红黑树的正确性。