请用c++编写创建红黑树代码

### 回答1：

红黑树是一种自平衡二叉查找树，它能够保证任何一棵子树的最大高度为O（log n）。c语言可以用来创建红黑树，以下是一个简单的实现：/* 用C语言实现红黑树 */
#include <stdio.h>
#include <stdlib.h>

struct Node
{
int key;
struct Node *left, *right, *parent;
int color;
};

/* 初始化Node */
struct Node *NIL;
struct Node *root = NIL;

/* 设置新节点 */
struct Node* newNode(int key)
{
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->key = key;
temp->left = temp->right = temp->parent = NIL;
temp->color = 1; /* 1 for red, 0 for black */
return temp;
}

/* 将节点插入红黑树 */
void insert(int key)
{
struct Node *temp = newNode(key);
struct Node *x = root;
struct Node *y = NIL;

while (x != NIL)
{
y = x;
if (temp->key < x->key)
x = x->left;
else
x = x->right;
}
temp->parent = y;
if (y == NIL)
root = temp;
else if (temp->key < y->key)
y->left = temp;
else
y->right = temp;
temp->color = 1;
fixInsert(temp);
}

/* 修复红黑树 */
void fixInsert(struct Node *z)
{
struct Node *y;
while (z->parent->color == 1)
{
if (z->parent == z->parent->parent->left)
{
y = z->parent->parent->right;
if (y->color == 1)
{
z->parent->color = 0;
y->color = 0;
z->parent->parent->color = 1;
z = z->parent->parent;
}
else
{
if (z == z->parent->right)
{
z = z->parent;
rotateLeft(z);
}
z->parent->color = 0;
z->parent->parent->color = 1;
rotateRight(z->parent->parent);
}
}
else
{
y = z->parent->parent->left;
if (y->color == 1)
{
z->parent->color = 0;
y->color = 0;
z->parent->parent->color = 1;
z = z->parent->parent;
}
else
{
if (z == z->parent->left)
{
z = z->parent;
rotateRight(z);
}
z->parent->color = 0;
z->parent->parent->color = 1;
rotateLeft(z->parent->parent);
}
}
}
root->color = 0;
}

/* 左旋 */
void rotateLeft(struct Node *x)
{
struct Node *y = x->right;
x->right = y->left;
if (y->left != NIL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}

/* 右旋 */
void rotateRight(struct Node *x)
{
struct Node *y = x->left;
x->left = y->right;
if (y->right != NIL)
y->right->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
root = y;
else if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
y->right = x;
x->parent = y;
}

### 回答2：
红黑树是一种自平衡的二叉查找树，它的每个节点都带有一个额外的表示节点颜色的位，可以是红色或黑色。红黑树的性质如下：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶节点（NIL节点，空节点）是黑色。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

下面是使用C语言实现红黑树的基本代码：

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

typedef struct Node {
    int data;
    int color; // 0表示黑色，1表示红色
    struct Node *parent;
    struct Node *left;
    struct Node *right;
} Node;

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

void insert(Node **root, int data) {
    Node *newNode = createNode(data);
    if (*root == NULL) {
        newNode->color = 0; // 根节点为黑色
        *root = newNode;
    } else {
        Node *tempNode = *root;
        Node *parentNode = NULL;
        while (tempNode != NULL) {
            parentNode = tempNode;
            if (data < tempNode->data) {
                tempNode = tempNode->left;
            } else {
                tempNode = tempNode->right;
            }
        }
        newNode->parent = parentNode;
        if (data < parentNode->data) {
            parentNode->left = newNode;
        } else {
            parentNode->right = newNode;
        }
    }
}

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

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

    printf("红黑树的中序遍历结果为：");
    printTree(root);

    return 0;
}

上面的代码实现了红黑树的创建和插入操作，并输出了红黑树的中序遍历结果。你可以根据需要进行修改和扩展。

### 回答3：
红黑树是一种自平衡的二叉搜索树，通过对节点进行染色和旋转操作，保持树的平衡。下面是使用C语言编写一个创建红黑树的简单示例代码：

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

enum Color {RED, BLACK};

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

typedef struct RBT {
    Node *root;
    Node *NIL; // 空节点
} RBT;

RBT* createRBT() {
    RBT *rbt = (RBT*)malloc(sizeof(RBT));
    rbt->NIL = (Node*)malloc(sizeof(Node));
    rbt->NIL->color = BLACK; // 空节点为黑色
    rbt->root = rbt->NIL;
    return rbt;
}

Node* createNode(int key) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->color = RED; // 新插入的节点颜色为红色
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}
// 左旋操作
void leftRotate(RBT *rbt, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left != rbt->NIL)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == rbt->NIL)
        rbt->root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

// 右旋操作
void rightRotate(RBT *rbt, Node *y) {
    Node *x = y->left;
    y->left = x->right;
    if (x->right != rbt->NIL)
        x->right->parent = y;
    x->parent = y->parent;
    if (y->parent == rbt->NIL)
        rbt->root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
    x->right = y;
    y->parent = x;
}

void insertFixup(RBT *rbt, Node *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node *y = z->parent->parent->right;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(rbt, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(rbt, z->parent->parent);
            }
        } else {
            Node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(rbt, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(rbt, z->parent->parent);
            } 
        }
    }
    rbt->root->color = BLACK;
}

void insert(RBT *rbt, int key) {
    Node *z = createNode(key);
    Node *y = rbt->NIL;
    Node *x = rbt->root;

    // 找到插入位置
    while (x != rbt->NIL) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (y == rbt->NIL)
        rbt->root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
    z->left = rbt->NIL;
    z->right = rbt->NIL;
    z->color = RED;

    insertFixup(rbt, z);
}

int main() {
    RBT *rbt = createRBT();
    int i, n, key;

    printf("输入要插入的节点个数: ");
    scanf("%d", &n);
    printf("输入节点的值: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        insert(rbt, key);
    }

    printf("插入后的红黑树前序遍历结果: ");
    preorderTraversal(rbt->root);

    return 0;
}

这个示例代码演示了如何创建一个红黑树，并实现了插入操作。在插入操作中，根据红黑树的性质进行节点的旋转和染色操作来保持树的平衡。
请注意，在完整的红黑树代码中，还应包含其他辅助函数，如前序遍历、中序遍历、后序遍历等，以及删除操作和查找操作的实现。此处代码仅为简单示例，供参考。