作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
插入几个数字后,我遇到显示红黑树的问题。可能fixTree函数包含一些错误(插入数字后仅显示第一个数字= 38)。
有人知道出了什么问题吗?
#include <stdio.h>
#include <stdlib.h>
#define swap(type, i, j) {type t = i; i = j; j = t;}
typedef enum COLOR{
RED,
BLACK
} NodeColor;
typedef struct BST{
struct BST *up, *left, *right;
int key, color;
} RedBlackTree;
RedBlackTree *tree = NULL;
RedBlackTree *createNode(int key){
RedBlackTree *temp;
temp = (RedBlackTree*) malloc(sizeof(RedBlackTree));
temp->left = NULL;
temp->right = NULL;
temp->key = key;
temp->color = RED;
return temp;
}
void rotateLeft(RedBlackTree *root, RedBlackTree *temp){
RedBlackTree *rightSon = temp->right;
temp->right = rightSon->left;
if (temp->right != NULL){
temp->right->up = temp;
}
rightSon->up = temp->up;
if (temp->up == NULL){
root = rightSon;
}
else if (temp == temp->up->left){
temp->up->left = rightSon;
}
else{
temp->up->right = rightSon;
}
rightSon->left = temp;
temp->up = rightSon;
}
void rotateRight(RedBlackTree *root, RedBlackTree *temp){
RedBlackTree *leftSon = temp->left;
temp->left = leftSon->right;
if (temp->left != NULL){
temp->left->up = temp;
}
leftSon->up = temp->up;
if (temp->up == NULL){
root = leftSon;
}
else if (temp == temp->up->left){
temp->up->left = leftSon;
}
else{
temp->up->right = leftSon;
}
leftSon->right = temp;
temp->up = leftSon;
}
void fixTree(RedBlackTree *root, RedBlackTree *temp){
RedBlackTree *parent = NULL;
RedBlackTree *grandparent = NULL;
while ((temp != root) && (temp->color != BLACK) && (temp->up->color == RED)){
parent = temp->up;
grandparent = temp->up->up;
if (parent == grandparent->left){
RedBlackTree *uncle = grandparent->right;
if (uncle != NULL && uncle->color == RED){
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
temp = grandparent;
}
else{
if (temp == parent->right){
rotateLeft(root, parent);
temp = parent;
parent = temp->up;
}
rotateRight(root, grandparent);
swap(int, parent->color, grandparent->color);
temp = parent;
}
}
else{
RedBlackTree *uncle = grandparent->left;
if ((uncle != NULL) && (uncle->color == RED)){
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
temp = grandparent;
}
else{
if (temp == parent->left){
rotateRight(root, parent);
temp = parent;
parent = temp->up;
}
rotateLeft(root, grandparent);
swap(int, parent->color, grandparent->color);
temp = parent;
}
}
}
root->color = BLACK;
}
RedBlackTree *insertNode(RedBlackTree *root, RedBlackTree *temp){
if (root == NULL){
return temp;
}
if (temp->key < root->key){
root->left = insertNode(root->left, temp);
root->left->up = root;
}
else if (temp->key > root->key){
root->right = insertNode(root->right, temp);
root->right->up = root;
}
return root;
}
void insert(int key){
RedBlackTree *temp = createNode(key);
tree = insertNode(tree, temp);
fixTree(tree, temp);
}
void printTree(RedBlackTree *root){
if (root){
printTree(root->left);
printf("%d %s\n", root->key, root->color == 0 ? "RED" : "BLACK");
printTree(root->right);
}
}
int main(){
insert(38);
insert(31);
insert(22);
insert(8);
insert(20);
insert(5);
insert(10);
insert(9);
insert(21);
insert(27);
insert(29);
insert(25);
insert(28);
printTree(tree);
return 0;
}
最佳答案
void fixTree(RedBlackTree *root, RedBlackTree *temp)
您通过值传递根的地址,因此对 root
内部 fixTree
的任何更改在调用代码中将不可见。特别是 rotateLeft
和 rotateRight
,当您再次复制地址时,将不会修改调用代码中的变量。
您需要传递一个指向根指针的指针。这意味着你的原型(prototype)应该是
void fixTree(RedBlackTree **p_root, RedBlackTree *temp)
自然地,操作会进行调整,以便它们在 *p_root
上执行。例如rotateLeft
中的以下行:
*p_root = rightSon;
关于c - 红黑树 - fixTree 实现无法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42318223/
我正在实现红黑 SOR 的并行版本。 我想获得每个进程的最大误差的 MPI_Allreduce 部分不起作用。它永远不会改变,即使只有一个过程,它也会给出高于 2.0 的值。怎么回事?? 这是代码,有
我为拉普拉斯方程(一个简单的加热板问题)在我的红黑 Gauss-Seidel 求解器中添加了 OpenACC 指令,但是 GPU 加速的代码并不比 CPU 快,即使对于大问题也是如此。 我还编写了一个
我是一名优秀的程序员,十分优秀!