用c语言实现——一个交互式红黑树系统
一、知识要点
定义：
红黑树（Red-Black Tree）是一种自平衡二叉查找树。它在计算机科学中被广泛应用于需要动态数据集合的场景，能够在保持平衡的同时，支持高效的插入、删除和查找操作。
性质
性质：
1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL节点）是黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色。（红色节点不能有两个红色子节点）
5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，黑色节点的个数相同。
基本操作及时间复杂度：
插入：
新节点插入后，树可能失去平衡，需要通过旋转和重新着色来恢复平衡。
O(log n)，其中n是树中节点的数量。因为红黑树的高度保持在 logarithmic级别，插入操作需要常数次旋转和重新着色。
删除：
删除节点后，树可能失去平衡，同样需要通过旋转和重新着色来恢复平衡。
O(log n)，与插入类似，删除操作涉及常数次旋转和重新着色。
查找：
从根节点开始，根据目标值与当前节点值的大小关系，决定向左子树或右子树查找。
O(log n)，因为树的高度保持平衡，查找过程不会退化为线性搜索。
优点：
高效性：在保持平衡的情况下，所有基本操作（插入、删除、查找）都能在O(log n)时间内完成，适用于需要频繁动态修改数据的场景。
实用性：是一种折中的数据结构，比 AVL树插入和删除更快（因为 AVL树对平衡要求更严格），比普通二叉查找树更平衡，所以查找速度更快。
缺点：
实现复杂：比普通二叉树的实现复杂，需要处理旋转和颜色调整等操作。
空间开销：每个节点需要存储颜色信息，增加了少量的空间开销。
二、代码解析
Ⅰ结构体定义声明部分
1.红黑树中节点的结构Node
可以创建红黑树的节点，并利用节点的颜色和指针关系来维护红黑树的性质和结构。
一个Color的枚举类型，它有两个枚举值：RED和BLACK。这个枚举类型用于表示红黑树中节点的颜色属性。
一个结构体Node：
key：一个整数类型，表示节点存储的键值
color：Color类型的枚举变量，表示节点的颜色。
left：指向该节点左孩子节点的指针。
right：指向该节点右孩子节点的指针。
parent：指向该节点父节点的指针。
2.全局的NIL节点
定义了一个全局的NIL节点，用于红黑树的实现。
NIL_NODE是一个全局的Node结构体变量，用于表示红黑树中的NIL节点（也称为外部节点或哨兵节点或者叶子节点）。
NIL节点的初始化：
key：设置为0，具体值通常不重要。
color：设置为BLACK，因为红黑树的叶子节点（NIL节点）必须是黑色的。
left、right、parent：都指向自身（&NIL_NODE），形成一个自循环结构，方便树的操作和边界条件处理。
定义NIL指针：
NIL是一个指向Node的指针，初始化为指向NIL_NODE。
在整个红黑树的实现中，NIL用于表示空节点或叶子节点，所有的叶子节点都指向这个全局的NIL_NODE。
3.红黑树的结构体类型 RBTree
定义了一个红黑树的结构体类型 RBTree，用于表示红黑树本身。
root 是一个指向 Node 的指针，表示红黑树的根节点。
初始时，root 通常被设置为 NIL（即全局的NIL节点），表示树为空。
4.队列结构体定义Queue
定义了一个用于实现队列的结构体 Queue，主要用于层次遍历（广度优先遍历）红黑树。
items：一个指向 Node* 类型的指针数组，用于存储队列中的元素（节点指针）。
front：一个整数，表示队列的头部位置（即第一个元素的索引）。
rear：一个整数，表示队列的尾部位置（即最后一个元素的索引）。
capacity：一个整数，表示队列的最大容量。
在红黑树的层次遍历中，队列用于存储每一层的节点。从根节点开始，将节点依次入队，然后出队并访问节点，同时将节点的子节点入队。这样可以确保按层次顺序访问树中的所有节点。
Ⅱ函数操作部分
Queue队列操作部分
1. 队列的创建操作
函数功能：
create_queue 函数用于创建一个队列。
参数： capacity 指定队列的最大容量。
返回值：是一个指向 Queue 类型的指针，表示创建的队列。
内存分配：
使用 malloc 函数为 Queue 结构体分配内存。
如果内存分配失败（即 malloc 返回 NULL），函数直接返回 NULL。
初始化队列：
为队列的 items 成员分配内存，用于存储队列中的元素（节点指针）。
如果 items 的内存分配失败，函数返回 NULL。
初始化队列的 front 和 rear 指针为 -1，表示队列为空。
设置队列的容量为传入的 capacity 参数。
返回队列指针：
如果队列创建成功，返回指向新创建队列的指针。
提供了一个简单的队列创建函数，为后续的队列操作（如入队、出队等）奠定了基础。通过动态内存分配和初始化，可以灵活地在程序中使用队列数据结构。
2. 队列的入队操作
函数功能：
enqueue 函数用于将一个节点添加到队列的尾部。
参数 q 是指向队列的指针，node 是要入队的节点指针。
检查队列是否已满：
if (q->rear == q->capacity - 1) return;：检查队列是否已满。如果队列已满（即 rear 指针已到达队列的最大容量减一的位置），则直接返回，不进行任何操作。
初始化队列前端：
if (q->front == -1) q->front = 0;：如果队列当前为空（front 和 rear 都为 -1），则将 front 指针初始化为 0，表示队列的前端位置。
入队操作：
q->items[++q->rear] = node;：将 rear 指针递增 1，然后将新节点 node 放入队列的尾部位置。
3. 队列的出队操作
函数功能：
dequeue 函数用于从队列的头部移除并返回一个节点。
参数 q 是指向队列的指针。
返回值是一个指向 Node 类型的指针，表示出队的节点。如果队列为空，则返回 NIL。
检查队列是否为空：
if (is_empty(q)) return NIL;：调用 is_empty 函数检查队列是否为空。如果队列为空，返回 NIL。
获取队首元素：
Node* item = q->items[q->front];：获取队列头部的节点。
更新队列前端指针：
if (q->front == q->rear) q->front = q->rear = -1;：如果队列中只有一个元素（即 front 和 rear 相等），出队后将 front 和 rear 重置为 -1，表示队列为空。
else q->front++;：如果队列中还有其他元素，将 front 指针递增 1，指向新的队首元素。
返回出队元素：
return item;：返回出队的节点指针。
4.队列的判空操作
函数功能：
is_empty 函数用于检查队列是否为空。
参数 q 是指向队列的指针。
返回值是一个布尔值，表示队列是否为空。
逻辑：
通过检查队列的 front 指针是否为 -1 来判断队列是否为空。
如果 front 为 -1，表示队列为空，返回 true；否则返回 false。
5.队列内存释放操作
函数功能：
free_queue 函数用于释放队列占用的内存。
参数 q 是指向队列的指针。
逻辑：
首先释放队列中存储节点指针的数组 items。
然后释放队列结构体本身的内存。
Red-Black Tree红黑树操作部分
1.红黑树的核心操作函数
包括树的初始化和节点的创建
①初始化红黑树：
函数功能：
init_tree 函数用于初始化红黑树。
参数 tree 是指向红黑树的指针。
逻辑：
将红黑树的根节点设置为 NIL，表示树初始时为空。
初始化什么数据都没有输入，相当于在红黑树里面先放入了一个NULL叶子节点
② 创建红黑树节点：
函数功能：
create_node 函数用于创建一个新的红黑树节点。
参数： key 是节点的键值。
返回值：是一个指向新创建节点的指针，如果内存分配失败则返回 NULL。
逻辑：
使用 malloc 动态分配内存来创建新节点。
如果内存分配失败则返回 NULL。
初始化节点的键值为传入的 key（用户自己输入的数据值）。
设置节点的颜色为红色（红黑树的新节点默认为红色）。
设置节点的左子节点、右子节点和父节点为 NIL。
疑点：
新节点初始化为红色是因为红黑树的插入操作通常会将新节点添加为红色，以尽量减少对树平衡性的影响。如果添加的节点是黑色，可能会违反红黑树的性质，需要更复杂的调整操作。
2. 红黑树的左旋操作
结合具体示例：
假设我们有一棵简单的红黑树，树的结构如下：
节点 A 是根节点，颜色为黑色。
节点 B 是节点 A 的右子节点，颜色为红色。
所有叶子节点都是 NIL，颜色为黑色。
具体执行步骤：
①保存右子节点：
Node* y = x->right;：将节点 A 的右子节点 B 保存到变量 y 中。y 指向节点 B。
②调整子节点关系
x->right = y->left;：将节点 A 的右子节点更新为 B 的左子节点（NIL）。
if (y->left != NIL) y->left->parent = x;：由于 y->left 是 NIL，跳过。
假如y（B）->left不为NULL，为有实际值，就执行让y->left的父亲节点指向x。
③调整父节点关系：
y->parent = x->parent;：将 B 的父节点设置为 A 的父节点（NIL）。
if (x->parent == NIL) tree->root = y;：由于 A 是根节点，现在进行左旋之后，将树的根节点更新为 B。
④完成旋转：
y->left = x;：将 A 设为 B 的左子节点。
x->parent = y;：将 A 的父节点设为 B。
左旋后的树结构
通过左旋操作，节点 y 上升，节点 x 下降，树的结构发生变化但仍然保持二叉搜索（排序）树的性质。
3.红黑树的右旋操作
结合具体示例：
假设我们有一棵简单的红黑树，结构如下：
①保存左子节点：
Node* x = y->left;：将节点 B 的左子节点 A 保存到变量 x 中。
②调整子节点关系：
y->left = x->right;：将节点 B 的左子节点更新为 A 的右子节点（NIL）。
if (x->right != NIL) x->right->parent = y;：由于 x->right 是 NIL，跳过。
③调整父节点关系：
x->parent = y->parent;：将节点 A 的父节点设置为节点 B 的父节点（NIL）。
if (y->parent == NIL) tree->root = x;：由于 B 是根节点，将树的根节点更新为节点 A。
④完成旋转：
x->right = y;：将节点 B 设置为节点 A 的右子节点。
y->parent = x;：将节点 B 的父节点设置为节点 A。
4.红黑树的插入修复操作
函数功能：
修复红黑树在插入新节点后的性质。
参数：
RBTree* tree：指向红黑树的指针。
Node* z：指向新插入节点的指针。
无返回值。
功能：检查新插入节点 z 的父节点是否为红色。如果是，进入循环进行修复。
逻辑：红黑树不允许两个连续的红节点，因此需要修复。
功能：判断 z 的父节点是其祖父节点的左子节点还是右子节点。这里是当为左节点的情况。
逻辑：根据父节点的位置，选择不同的修复策略。
功能：获取 z 的叔叔节点（父节点的兄弟节点）。
逻辑：叔叔节点的颜色会影响修复策略。
功能：检查叔叔节点是否为红色。
逻辑：如果叔叔节点是红色，执行颜色翻转。
功能：颜色翻转操作。
逻辑：父节点和叔叔节点变黑，祖父节点变红，问题上移至祖父节点。
功能：处理叔叔节点为黑色的情况。
逻辑：需要进行旋转操作。
功能：调整 z 的位置并进行左旋。
逻辑：将 z 转换为父节点的左子节点，以便进行后续的右旋操作。
功能：颜色调整和右旋操作。
逻辑：调整颜色后进行右旋，重新平衡树。
功能：处理父节点为右子节点的情况。
逻辑：与左子节点的情况对称。
功能：获取叔叔节点。
逻辑：父节点为右子节点时，叔叔节点是祖父节点的左子节点。
功能：检查叔叔节点是否为红色。
逻辑：颜色翻转操作。
功能：颜色翻转。
逻辑：与父节点为左子节点的情况类似。
功能：处理叔叔节点为黑色的情况。
逻辑：需要进行旋转操作。
功能：调整 z 的位置并进行右旋。
逻辑：将 z 转换为父节点的右子节点，以便进行后续的左旋操作。
功能：颜色调整和左旋操作。
逻辑：调整颜色后进行左旋，重新平衡树。
功能：确保红黑树的根节点始终为黑色。
逻辑：红黑树的性质要求根节点必须是黑色。
总结：
-
叔叔节点为红色：颜色翻转，问题上移。
-
叔叔节点为黑色，且
z是父节点的外侧子节点：进行旋转操作，调整树的结构。 -
叔叔节点为黑色，且
z是父节点的内侧子节点：先调整z的位置，再进行旋转操作。
外侧子节点（或称为外孙子节点）
是指节点 z 位于其父节点的与父节点在祖父节点中的相反位置。具体来说，如果父节点是祖父节点的左子节点，而节点 z 是父节点的右子节点，或者父节点是祖父节点的右子节点，而节点 z 是父节点的左子节点，那么节点 z 就是外侧子节点。
内侧子节点（inside child）
是指节点 z 与其父节点位于祖父节点的同一侧。也就是说：
如果父节点是祖父节点的左子节点，且节点 z 是父节点的左子节点。
或者父节点是祖父节点的右子节点，且节点 z 是父节点的右子节点。
5. 红黑树的插入操作
参数：
RBTree* tree：指向红黑树的指针。
int key：要插入节点的键值。
1.创建新节点：
调用 create_node 函数创建一个新节点 z，键值为 key，颜色默认为红色。
2.初始化辅助变量：
y 用于记录最终的父节点，初始化为 NIL。
x 用于遍历树以找到插入位置，初始化为树的根节点。
3. 寻找插入位置：
当 x 不为 NIL 时，循环继续。
将当前节点 x 保存到 y 中，作为潜在的父节点。
如果 z 的键值小于 x 的键值，移动到左子节点。
否则，移动到右子节点。
循环直到找到一个 NIL 节点，此时 y 指向新节点的父节点。
4.设置新节点的父节点：
将新节点 z 的父节点设置为找到的父节点 y。
5.插入新节点：
如果树为空（y 为 NIL），将新节点 z 设置为根节点。
否则，如果 z 的键值小于父节点 y 的键值，将 z 插入到 y 的左子节点。
否则，将 z 插入到 y 的右子节点。
6.修复红黑树性质：
调用 insert_fixup 函数修复红黑树的性质，确保树保持平衡。
6.红黑树的替换操作
函数功能：
将节点 u 替换为节点 v，在红黑树中用 v 替换 u 的位置。
参数：
RBTree* tree：指向红黑树的指针，表示操作在哪棵树上进行。
Node* u：指向要被替换的节点。
Node* v：指向用来替换的节点。
没有返回值。
1.判断 u 是否为根节点：
如果 u 是根节点（即其父节点为 NIL），直接将树的根节点替换为 v。
2.判断 u 是父节点的左子节点还是右子节点：
如果 u 是其父节点的左子节点，则将父节点的左子节点替换为 v。
否则，将父节点的右子节点替换为 v。
3.更新 v 的父节点：
将 v 的父节点设置为 u 的父节点，以维护树的结构。
逻辑总结：
该函数的作用是用节点 v 替换节点 u，确保替换后树的结构正确。
替换操作包括更新父节点的子节点指针以及更新 v 的父节点指针。
这个操作在红黑树的插入和删除操作中会用到，用于调整树的结构。
7.找最小键值节点操作
参数说明：
Node* node：指向红黑树中某个节点的指针，表示从该节点开始查找最小节点。
循环查找左子节点：
由于红黑树是二叉搜索树，左子节点的键值总是小于父节点的键值。
因此，最小节点必定是树的最左节点。
循环遍历，不断向左移动，直到左子节点为 NIL。
当循环结束时，node 指向最左节点，即为最小键值节点。
8.红黑树的删除修复操作
当从红黑树中删除一个节点时，可能会破坏上述性质。特别是，如果删除的节点是黑色的，会导致其父节点到子节点的路径上黑色节点数目减少一个，从而违反黑路同性质。此外，删除操作后可能会出现红色节点有两个红色子节点的情况，从而违反不连红性质。delete_fixup 函数的作用就是修复这些问题。
修复函数的核心逻辑：
删除黑色节点会导致其所在路径的黑高（Black Height）减少1，从而违反红黑树的性质5。替代节点 x 的颜色决定了修复的复杂程度：
-
x是红色：直接染黑即可恢复黑高。 -
x是黑色：需要进一步调整结构以平衡黑高。
具体场景与示例：
场景1：x 是红色
操作：
-
删除黑色节点后，
x成为其父节点的子节点。 -
将
x染黑。 -
效果：被删除路径的黑高恢复，且不会引入连续红节点。
示例：
假设删除以下红黑树中的黑色节点 B (5)，其替代节点 x 是红色节点 R (3)：
删除后结构：
修复操作：将 x（即 R (3)）染黑：
结果：所有路径的黑高均为2，满足红黑树性质。
场景2：x 是黑色
操作：
-
删除黑色节点后，
x的路径黑高减少1。 -
需要通过旋转和染色调整兄弟节点及其子节点的颜色，重新平衡黑高。
主要处理以下几种情况：
-
兄弟节点是红色：这是最简单的情况，只需要进行颜色翻转和旋转操作即可。
-
兄弟节点是黑色且其子节点都是黑色：这种情况下，兄弟节点需要承担原本属于被删除节点的“黑色深度”，但由于兄弟节点已经是黑色，所以需要将其变为红色，并将问题上移至父节点。
-
兄弟节点是黑色且至少有一个红色子节点：这种情况下，需要进行旋转和颜色调整，将红色子节点变为黑色，并调整父节点和兄弟节点的颜色。
函数入口条件：
只有当 x 是黑色且不是根节点时，才需要修复（根节点可直接染黑）。
场景1：兄弟节点 w 是红色
目标：将兄弟节点变为黑色，方便后续操作。
操作：
-
将
w染黑，父节点染红。 -
左旋父节点，使
w成为祖父节点。 -
更新
w为父节点的新右子节点（此时w必为黑色）。
示意图：
场景2：兄弟节点 w 的子节点均为黑色
目标：通过将 w 染红，将父节点作为新的 x 继续修复。
原理：
-
将
w染红后，父节点的子树黑高恢复平衡。 -
但父节点可能变为“双重黑”，需要继续向上处理。
场景3：兄弟节点 w 的右子节点为黑色（左子节点为红）
目标：将 w 的右子节点变为红色，转换为场景4。
操作：
-
将
w的左子节点染黑，w染红。 -
右旋
w，使w的左子节点成为新的兄弟节点。
示意图：
场景4：兄弟节点 w 的右子节点为红色
目标：通过旋转和染色，彻底解决黑高问题。
操作：
-
将
w染为父节点的颜色。 -
父节点染黑，
w的右子节点染黑。 -
左旋父节点，使
w成为新的父节点。 -
将
x设为根节点，终止循环。
9.红黑树的删除操作
红黑树的删除分为两步：①首先执行普通二叉搜索树的删除，②然后通过修复函数调整颜色和结构以保持红黑树的性质。
1.函数逻辑概述：
目标：删除指定键值的节点 z，并维护红黑树性质。
关键步骤：
-
查找待删除节点
z。 -
处理
z的子节点（0、1或2个子节点）。 -
若被删除节点
y原为黑色，调用delete_fixup修复平衡。
2.代码逐行解析
2.1 查找待删除节点
通过 search 找到目标节点 z，若未找到直接返回。
2.2 初始化变量
关键点：
y 最终可能为 z 或其后继节点（若 z 有两个子节点）。
y_original_color 决定是否需要修复。
2.3 处理子节点情况
Case 1: z 只有右子节点
用 z->right 替换 z，x 指向替代节点。
Case 2: z 只有左子节点
用 z->left 替换 z，x 指向替代节点。
Case 3: z 有两个子节点
关键逻辑：
-
找到
z的后继节点y（右子树的最小节点）。 -
若
y不是z的直接右子节点，需将y的右子树移植到y的原位置。 -
用
y替换z，并继承z的颜色。 -
x指向y的右子节点（可能是NIL）。
2.4 修复红黑树性质
条件：若被删除的节点 y 原为黑色，需调用 delete_fixup 修复黑高失衡。
原因：删除黑色节点会减少路径黑高，可能违反性质5。
2.5 释放节点
确保 z 的所有指针已正确转移，避免内存泄漏。
3. 示例分析：
假设删除以下红黑树中的节点 B (20)：
-
查找
z = B (20)，其右子节点为B (25)，左子节点为R (15)。 -
找到
y = minimum(z->right) = B (25)。 -
用
y = B (25)替换z = B (20)，并继承其颜色。 -
由于
y_original_color = BLACK，调用delete_fixup修复。
10. 找最大键值节点操作
找到以 node 为根的子树中的最大值节点。
在二叉搜索树中，最大值节点位于最右路径的末端，逻辑正确。
11. 查前驱节点操作
情况1：节点有左子树
-
操作：直接返回左子树的最大值节点。
-
原理：在二叉搜索树中，左子树的最大值节点是当前节点的前驱。
情况2：节点无左子树
-
操作：向上查找第一个祖先节点
y，使得x位于y的右子树中。 -
原理：若
x是父节点的左子节点，说明父节点比x大，需继续向上找更小的祖先。 -
终止条件：
-
当
y为根节点且x是左子节点时，循环结束后返回NIL（无前驱）。 -
当
x是某个祖先节点的右子节点时，该祖先节点即为前驱。
-
12. 查后继节点操作
情况1：节点有右子树
-
操作：直接返回右子树的最小值节点。
-
原理：在二叉搜索树中，右子树的最小值节点是当前节点的后继。
情况2：节点无右子树
-
操作：向上查找第一个祖先节点
y，使得x位于y的左子树中。 -
原理：若
x是父节点的右子节点，说明父节点比x小，需继续向上找更大的祖先。 -
终止条件：
-
当
y为根节点且x是右子节点时，循环结束后返回NIL（无后继）。 -
当
x是某个祖先节点的左子节点时，该祖先节点即为后继。
-
13.树形打印输出
node：指向树的节点的指针，函数从这个节点开始打印树的结构。函数通过递归调用自身来遍历树的各个节点。
level：表示当前节点所在的层级，初始调用时一般传入 0 或 1，随着递归的深入，每向下一层，level 增加 1，用于控制打印时的缩进，以体现树的层次关系。
代码逻辑分析
-
判断节点是否为空 ：首先判断传入的节点是否为
NIL（空节点），如果是空节点则直接返回，不进行任何操作，这是递归终止条件之一，避免对空节点进行无效操作。 -
递归打印右子树 ：如果节点不是空节点，则首先递归调用
print_tree函数打印该节点的右子树，传入的层级为level + 1，表示右子树的节点比当前节点层级深一层，这样在打印时右子树会在更右边的位置显示，符合树的结构特点。 -
打印当前节点信息 ：
-
通过一个
for循环，根据当前节点的层级level打印相应数量的空格，实现节点信息的缩进，层级越高，缩进越多，从而在视觉上体现树的层次关系，使打印出的树结构更加清晰易读。 -
使用
printf函数打印当前节点的键值node->key和颜色信息。颜色信息通过三元运算符判断，如果节点颜色为红色则输出 "R"，否则输出 "B"，这表明该函数可能是用于打印红黑树等具有颜色属性的树结构。
-
-
递归打印左子树 ：在打印完当前节点信息后，递归调用
print_tree函数打印该节点的左子树，同样传入的层级为level + 1，与打印右子树的逻辑类似，左子树的节点也会在更右边的位置显示，但由于是先打印右子树再打印左子树，所以在同一层级上，右子树会先于左子树被打印出来，这可能与某些特定树的遍历顺序（如后序遍历的变种）有关。
14. 层次打印输出
root：树的根节点指针，函数从该节点开始遍历。
代码逻辑分析
-
空树判断：若根节点为空，直接返回，结束函数执行。
-
队列初始化：创建一个容量为100的队列，并将根节点入队。
-
遍历循环：只要队列不为空，就持续执行以下操作：
-
节点出队：从队列中取出队首节点，存储在变量
current中。 -
打印节点信息：输出当前节点的键值和颜色（红或黑）。
-
子节点入队：如果当前节点的左子节点不为空，将其入队；同理，若右子节点不为空，也入队。
-
-
结束操作：遍历结束后，输出换行符，释放队列内存。
15. 释放树空间操作
流程分析：
-
判断节点是否为空：首先检查当前节点是否为
NIL（空节点）。如果是空节点，直接返回，不进行任何操作。这是递归终止的条件，避免对空节点进行无效操作。 -
递归释放左子树内存：如果当前节点不是空节点，则递归调用
free_tree函数释放当前节点左子节点的内存。通过这种方式，函数会一直递归到最左边的叶子节点。 -
递归释放右子树内存：在释放完左子树的内存后，递归调用
free_tree函数释放当前节点右子节点的内存。这确保了在释放当前节点之前，其左右子树的所有节点内存都已被释放。 -
释放当前节点内存：当左右子树的内存都释放完毕后，使用
free函数释放当前节点所占用的内存。这一步是后序遍历的一部分，确保了在释放父节点内存之前，其子节点的内存已经被释放。
Ⅲ文件操作部分
1. 文件操作
node：指向树的节点的指针，函数从这个节点开始保存信息。
fp：文件指针，指向要保存数据的文件，用于文件写入操作。
逻辑分析
-
判断是否为空：首先检查当前节点是否为
NIL，如果是，则直接返回，停止递归调用。 -
写入节点信息：利用
fprintf函数将当前节点的键值和颜色写入文件。键值和颜色分别以整型和字符型输出，格式化占位符为%d和%d。 -
递归处理子节点：依次对当前节点的左子节点和右子节点调用
save_tree函数。通过递归，函数能够遍历整个树，并将所有节点的信息按顺序写入文件。
2. 红黑树保存到文件操作
参数：
tree：指向红黑树的指针，包含了树的根节点等信息，是需要保存的树结构。
filename：一个 C 字符串，指定了要保存数据的文件的文件名。
流程分析
-
打开文件：通过
fopen函数以写模式打开指定的文件。如果文件不存在，则会创建一个新文件；如果文件已存在，则会截断文件，即删除文件中现有的所有内容。 -
错误检查：检查文件指针
fp是否为NULL。如果fp是NULL，说明文件打开失败，通过perror函数输出错误信息 "Error opening file"，并返回，结束函数执行。 -
保存树数据：如果文件打开成功，则调用
save_tree函数，将树的根节点和文件指针作为参数传递，开始递归地将树中的节点信息保存到文件中。 -
关闭文件：调用
fclose函数关闭文件，释放与文件相关的资源，确保数据正确写入文件系统。
3. 从文件加载红黑树数据的操作
参数
tree：指向红黑树结构的指针，表示要加载数据的目标树。
filename：一个 C 字符串，指定了包含红黑树数据的文件的文件名。
流程分析
-
打开文件：使用
fopen函数以只读模式打开指定的文件。如果文件不存在或无法打开，fopen将返回NULL。 -
错误处理：检查文件指针
fp是否为NULL。如果是，则输出错误信息并返回，终止函数执行。 -
清空现有树：调用
free_tree函数释放树中现有节点的内存，并将树的根节点设置为NIL，为加载新数据做好准备。 -
读取并插入数据：使用
fscanf_s函数从文件中逐行读取键值和颜色信息。对于每一行成功读取的数据，调用insert函数将键值插入到树中。 -
更新节点颜色：在插入键值后，通过
search函数找到刚插入的节点，并根据读取的颜色信息更新该节点的颜色。 -
关闭文件：完成数据加载后，调用
fclose函数关闭文件，释放文件资源。
三、完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
typedef enum { RED, BLACK } Color;
typedef struct Node
{
int key;
Color color;
struct Node* left;
struct Node* right;
struct Node* parent;
} Node;
// 全局NIL节点
Node NIL_NODE = { 0, BLACK, &NIL_NODE, &NIL_NODE, &NIL_NODE };
Node* NIL = &NIL_NODE;
typedef struct
{
Node* root;
} RBTree;
// 队列结构用于层次遍历
typedef struct
{
Node** items;
int front;
int rear;
int capacity;
} Queue;
// 函数声明
Queue* create_queue(int capacity);
void enqueue(Queue* q, Node* node);
Node* dequeue(Queue* q);
bool is_empty(Queue* q);
void free_queue(Queue* q);
void init_tree(RBTree* tree);
Node* create_node(int key);
void left_rotate(RBTree* tree, Node* x);
void right_rotate(RBTree* tree, Node* y);
void insert_fixup(RBTree* tree, Node* z);
void insert(RBTree* tree, int key);
void transplant(RBTree* tree, Node* u, Node* v);
Node* minimum(Node* node);
void delete_fixup(RBTree* tree, Node* x);
void delete(RBTree* tree, int key);
Node* search(Node* node, int key);
Node* predecessor(Node* x);
Node* successor(Node* x);
void print_tree(Node* node, int level);
void level_order_traversal(Node* root);
void save_tree(Node* node, FILE* fp);
void save_to_file(RBTree* tree, const char* filename);
void load_from_file(RBTree* tree, const char* filename);
void free_tree(Node* node);
void menu(RBTree* tree);
// 队列操作实现
Queue* create_queue(int capacity)
{
Queue* q = (Queue*)malloc(sizeof(Queue));
if (q == NULL)
{
return NULL;
}
q->items = (Node**)malloc(capacity * sizeof(Node*));
if (q->items == NULL)
{
return NULL;
}
q->front = q->rear = -1;
q->capacity = capacity;
return q;
}
void enqueue(Queue* q, Node* node)
{
if (q->rear == q->capacity - 1) return;
if (q->front == -1) q->front = 0;
q->items[++q->rear] = node;
}
Node* dequeue(Queue* q)
{
if (is_empty(q))
return NIL;
Node* item = q->items[q->front];
if (q->front == q->rear)
q->front = q->rear = -1;
else
q->front++;
return item;
}
bool is_empty(Queue* q)
{
return q->front == -1;
}
void free_queue(Queue* q)
{
free(q->items);
free(q);
}
// 红黑树核心操作
void init_tree(RBTree* tree)
{
tree->root = NIL;
}
Node* create_node(int key)
{
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL)
{
return NULL;
}
node->key = key;
node->color = RED;
node->left = NIL;
node->right = NIL;
node->parent = NIL;
return node;
}
void left_rotate(RBTree* tree, Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != NIL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
tree->root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void right_rotate(RBTree* tree, Node* y)
{
Node* x = y->left;
y->left = x->right;
if (x->right != NIL)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NIL)
tree->root = x;
else if (y == y->parent->right)
y->parent->right = x;
else
y->parent->left = x;
x->right = y;
y->parent = x;
}
void insert_fixup(RBTree* tree, 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;
left_rotate(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(tree, 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;
right_rotate(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(tree, z->parent->parent);
}
}
}
tree->root->color = BLACK;
}
void insert(RBTree* tree, int key)
{
Node* z = create_node(key);
Node* y = NIL;
Node* x = tree->root;
while (x != NIL)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == NIL)
tree->root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
insert_fixup(tree, z);
}
void transplant(RBTree* tree, Node* u, Node* v)
{
if (u->parent == NIL)
tree->root = v;
else if (u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
v->parent = u->parent;
}
Node* minimum(Node* node)
{
while (node->left != NIL)
node = node->left;
return node;
}
void delete_fixup(RBTree* tree, Node* x)
{
while (x != tree->root && x->color == BLACK)
{
if (x == x->parent->left)
{
Node* w = x->parent->right;
if (w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
left_rotate(tree, x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->right->color == BLACK)
{
w->left->color = BLACK;
w->color = RED;
right_rotate(tree, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
left_rotate(tree, x->parent);
x = tree->root;
}
}
else
{
Node* w = x->parent->left;
if (w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
right_rotate(tree, x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->left->color == BLACK)
{
w->right->color = BLACK;
w->color = RED;
left_rotate(tree, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
right_rotate(tree, x->parent);
x = tree->root;
}
}
}
x->color = BLACK;
}
void delete(RBTree* tree, int key)
{
Node* z = search(tree->root, key);
if (z == NIL)
return;
Node* y = z;
Node* x;
Color y_original_color = y->color;
if (z->left == NIL)
{
x = z->right;
transplant(tree, z, z->right);
}
else if (z->right == NIL)
{
x = z->left;
transplant(tree, z, z->left);
}
else
{
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z)
x->parent = y;
else
{
transplant(tree, y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(tree, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (y_original_color == BLACK)
delete_fixup(tree, x);
free(z);
}
Node* search(Node* node, int key)
{
while (node != NIL && key != node->key)
{
if (key < node->key)
node = node->left;
else
node = node->right;
}
return node;
}
Node* maximum(Node* node)
{
while (node->right != NIL)
node = node->right;
return node;
}
Node* predecessor(Node* x)
{
if (x->left != NIL)
return maximum(x->left);
Node* y = x->parent;
while (y != NIL && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
Node* successor(Node* x)
{
if (x->right != NIL)
return minimum(x->right);
Node* y = x->parent;
while (y != NIL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
// 树形打印
void print_tree(Node* node, int level)
{
if (node != NIL)
{
print_tree(node->right, level + 1);
for (int i = 0; i < level; i++)
printf(" ");
printf("%d(%s)\n", node->key, node->color == RED ? "R" : "B");
print_tree(node->left, level + 1);
}
}
// 层次遍历
void level_order_traversal(Node* root)
{
if (root == NIL)
return;
Queue* q = create_queue(100);
enqueue(q, root);
while (!is_empty(q))
{
Node* current = dequeue(q);
printf("%d(%s) ", current->key, current->color == RED ? "R" : "B");
if (current->left != NIL)
enqueue(q, current->left);
if (current->right != NIL)
enqueue(q, current->right);
}
printf("\n");
free_queue(q);
}
// 文件操作
void save_tree(Node* node, FILE* fp)
{
if (node == NIL) return;
fprintf(fp, "%d %d\n", node->key, node->color);
save_tree(node->left, fp);
save_tree(node->right, fp);
}
void save_to_file(RBTree* tree, const char* filename)
{
FILE* fp = fopen(filename, "w");
if (fp == NULL)
{
perror("Error opening file");
return;
}
save_tree(tree->root, fp);
fclose(fp);
}
void load_from_file(RBTree* tree, const char* filename)
{
FILE* fp = fopen(filename, "r");
if (fp == NULL)
{
perror("Error opening file");
return;
}
free_tree(tree->root);
tree->root = NIL;
int key = 0;
int color = 0;
while (fscanf_s(fp, "%d %d", &key, &color) == 2)
{
insert(tree, key);
Node* node = search(tree->root, key);
if (node != NIL)
node->color = color;
}
fclose(fp);
}
void free_tree(Node* node)
{
if (node == NIL)
return;
free_tree(node->left);
free_tree(node->right);
free(node);
}
// 交互菜单
void menu(RBTree* tree)
{
char filename[100];
int choice, key;
while (1)
{
printf("\n红黑树操作:> \n");
printf("1. 插入\n2. 删除\n3. 查找\n4. 打印树\n");
printf("5. 层次遍历\n6. 保存到文件\n7. 从文件加载\n");
printf("8. 查找前驱\n9. 查找后继\n0. 退出\n");
printf("请选择操作:>");
scanf_s("%d", &choice);
switch (choice)
{
case 1:
printf("请输入要插入的键值:> ");
scanf_s("%d", &key);
insert(tree, key);
break;
case 2:
printf("请输入要删除的键值:> ");
scanf_s("%d", &key);
delete(tree, key);
break;
case 3:
printf("请输入要查找的键值:> ");
scanf_s("%d", &key);
Node* result = search(tree->root, key);
if (result != NIL)
printf("Key %d found\n", key);
else
printf("Key not found\n");
break;
case 4:
print_tree(tree->root, 0);
break;
case 5:
level_order_traversal(tree->root);
break;
case 6:
printf("请输入文件名:> ");
scanf_s("%99s", filename, (unsigned)_countof(filename));
save_to_file(tree, filename);
break;
case 7:
printf("请输入文件名:> ");
scanf_s("%s", filename, (unsigned)_countof(filename));
load_from_file(tree, filename);
break;
case 8:
printf("请输入键值:> ");
scanf_s("%d", &key);
result = search(tree->root, key);
if (result == NIL)
{
printf("Key not found\n");
}
else
{
Node* pred = predecessor(result);
if (pred != NIL)
printf("前驱:> %d\n", pred->key);
else
printf("没有前驱\n");
}
break;
case 9:
printf("请输入键值:> ");
scanf_s("%d", &key);
result = search(tree->root, key);
if (result == NIL)
{
printf("未找到键值\n");
}
else
{
Node* succ = successor(result);
if (succ != NIL)
printf("后继:> %d\n", succ->key);
else
printf("没有后继\n");
}
break;
case 0:
free_tree(tree->root);
exit(0);
default:
printf("无效选择\n");
}
}
}
int main()
{
RBTree tree;
init_tree(&tree);
menu(&tree);
return 0;
}
用c语言实现一个交互式红黑树系统，支持用户自行创建红黑树，查找，插入，删除，寻找指定节点前驱和后继 ，以树的形式遍历输出，以层次结构遍历输出，保存到文件等一系列完整的基本操作的算法实现。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
34
0- 0
已为社区贡献3条内容
所有评论(0)