作者superme7 (Bonbodi)
看板C_and_CPP
标题[问题] 红黑树construct设root = nil遇到的问题
时间Tue Apr 27 21:17:26 2021
开发平台(Platform): (Ex: Win10, Linux, ...)
Win10
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
GCC
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
无
问题(Question)：
RBT，Tree的construct把root = nil，Insert node 後 root 无法更新 依然指向nil
喂入的资料(Input)：
在int main 中
预的正确确结果(Expected Output)：
Black/5 Black/8 Red/11 Black/9
错误结果(Wrong Output)：
没有显示
程式码(Code)：(请善用置底文网页, 记得排版，禁止使用图档)
#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
int key;
Node* p, * left, * right;
string color;
Node() :key(0), p(0), left(0), right(0), color("") {};
Node(int a) :key(a), left(0), right(0), p(0), color("") {};
};
class Tree
{
public:
Node* nil;
Node* root;
Tree()
{
nil = new Node;
nil->color = "black";
root = nil;
root->p = nil;
}
};
void left_Rotate(Tree t, Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != t.nil)
y->left->p = x;
if (x->p == t.nil)
t.root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->p = x->p;
y->left = x;
x->p = y;
}
void right_Rotate(Tree t, Node* x)
{
Node* y = x->left;
x->left = y->right;
if (y->right != t.nil)
y->right->p = x;
if (x->p == t.nil)
t.root = y;
else if (x->p->left == x)
y = x->p->left;
else
y = x->p->right;
y->p = x->p;
y->right = x;
x->p = y;
}
void InsertFixup(Tree t, Node* z)
{
while (z->p->color == "red")
{
if (z->p == z->p->p->left)
{
Node* y = z->p->p->right;
if (y->color == "red")
{
y->color = "black";
z->p->color = "black";
z->p->p->color = "red";
z = z->p->p;
}
else
{
if (z == z->p->right)
{
z = z->p;
left_Rotate(t, z);
}
z->p->color = "black";
z->p->p->color = "red";
right_Rotate(t, z->p->p);
}
}
else
{
Node* y = z->p->p->left;
if (y->color == "red")
{
y->color = "black";
y->p->p->color = "red";
z->p->color = "black";
z = z->p->p;
}
else
{
if (z == z->p->left)
{
z = z->p;
right_Rotate(t, z);
}
z->p->color = "black";
z->p->p->color = "red";
left_Rotate(t, z->p->p);
}
}
}
t.root->color = "black";
}
void Insert(Tree t, Node* z)
{
Node* y = t.nil;
Node* x = t.root;
while (x != t.nil)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y == t.nil)
t.root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->color = "red";
z->left = t.nil;
z->right = t.nil;
InsertFixup(t, z);
}
void Inorder(Tree t, Node* z)
{
if (z != t.nil)
{
Inorder(t, z->left);
cout << z->color << "/" << z->key << " ";
Inorder(t, z->right);
}
}
int main()
{
Tree a;
Node* b = new Node(8);
Node* c = new Node(11);
Node* d = new Node(9);
Node* e = new Node(5);
Insert(a, b);
Insert(a, c);
Insert(a, d);
Insert(a, e);
Inorder(a,a.root);
return 0;
}
补充说明(Supplement)：
我在想root是不是还是指向nil，所以Inorder Print不出来
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.220 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1619529448.A.DB4.html
1F：推 LPH66: 对, 因为你的 Tree 是传值传进去的, 里面更新没有传出来 04/28 02:41
2F：→ LPH66: 看你要传它的指标还是要改成传参考 04/28 02:41
3F：→ superme7: 对吼 谢谢L大 04/28 09:05