贊助廠商

娛樂城推薦

首頁

電腦與網際網路/其他:電腦列表

C/C++- 紅黑樹construct設root = nil遇到的問題

開發平台(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不出來--
  • 發問日期:2021-06-08 02:40:03

友站連結