C语言红黑树算法实现 - 代码示例和详解

#include <stdio.h>\n#include <stdlib.h>\n\n// 定义红黑树的颜色\ntypedef enum { RED, BLACK } Color;\n\n// 定义红黑树节点\ntypedef struct Node {\n int data;\n struct Node* parent;\n struct Node* left;\n struct Node* right;\n Color color;\n} Node;\n\n// 创建红黑树节点\nNode* createNode(int data) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->data = data;\n newNode->parent = NULL;\n newNode->left = NULL;\n newNode->right = NULL;\n newNode->color = RED;\n return newNode;\n}\n\n// 左旋操作\nvoid leftRotate(Node** root, Node* node) {\n Node* rightChild = node->right;\n node->right = rightChild->left;\n if (rightChild->left != NULL) {\n rightChild->left->parent = node;\n }\n rightChild->parent = node->parent;\n if (node->parent == NULL) {\n root = rightChild;\n } else if (node == node->parent->left) {\n node->parent->left = rightChild;\n } else {\n node->parent->right = rightChild;\n }\n rightChild->left = node;\n node->parent = rightChild;\n}\n\n// 右旋操作\nvoid rightRotate(Node* root, Node* node) {\n Node* leftChild = node->left;\n node->left = leftChild->right;\n if (leftChild->right != NULL) {\n leftChild->right->parent = node;\n }\n leftChild->parent = node->parent;\n if (node->parent == NULL) {\n root = leftChild;\n } else if (node == node->parent->left) {\n node->parent->left = leftChild;\n } else {\n node->parent->right = leftChild;\n }\n leftChild->right = node;\n node->parent = leftChild;\n}\n\n// 修正红黑树属性\nvoid fixup(Node* root, Node* node) {\n while (node != root && node->parent->color == RED) {\n if (node->parent == node->parent->parent->left) {\n Node uncle = node->parent->parent->right;\n if (uncle != NULL && uncle->color == RED) {\n node->parent->color = BLACK;\n uncle->color = BLACK;\n node->parent->parent->color = RED;\n node = node->parent->parent;\n } else {\n if (node == node->parent->right) {\n node = node->parent;\n leftRotate(root, node);\n }\n node->parent->color = BLACK;\n node->parent->parent->color = RED;\n rightRotate(root, node->parent->parent);\n }\n } else {\n Node* uncle = node->parent->parent->left;\n if (uncle != NULL && uncle->color == RED) {\n node->parent->color = BLACK;\n uncle->color = BLACK;\n node->parent->parent->color = RED;\n node = node->parent->parent;\n } else {\n if (node == node->parent->left) {\n node = node->parent;\n rightRotate(root, node);\n }\n node->parent->color = BLACK;\n node->parent->parent->color = RED;\n leftRotate(root, node->parent->parent);\n }\n }\n }\n (root)->color = BLACK;\n}\n\n// 插入节点\nvoid insert(Node* root, int data) {\n Node* newNode = createNode(data);\n Node* current = root;\n Node parent = NULL;\n while (current != NULL) {\n parent = current;\n if (newNode->data < current->data) {\n current = current->left;\n } else {\n current = current->right;\n }\n }\n newNode->parent = parent;\n if (parent == NULL) {\n root = newNode;\n } else if (newNode->data < parent->data) {\n parent->left = newNode;\n } else {\n parent->right = newNode;\n }\n fixup(root, newNode);\n}\n\n// 前序遍历红黑树\nvoid preorderTraversal(Node root) {\n if (root != NULL) {\n printf("%d ", root->data);\n preorderTraversal(root->left);\n preorderTraversal(root->right);\n }\n}\n\nint main() {\n Node* root = NULL;\n\n // 插入节点示例\n insert(&root, 10);\n insert(&root, 20);\n insert(&root, 30);\n insert(&root, 40);\n insert(&root, 50);\n insert(&root, 60);\n insert(&root, 70);\n\n // 前序遍历红黑树\n printf("前序遍历结果：");\n preorderTraversal(root);\n printf("\n");\n\n return 0;\n}\n