算法導論-紅黑樹C++實現

紅黑樹的定義：

一棵二叉查找樹如果滿足下面的紅黑性質，則為一棵紅黑樹：

1）每個節點或是紅的，或是黑的。
2）根節點是黑的。
3）每個葉節點（NIL）是黑節點。
4）如果一個節點是紅的，則它的兩個兒子都是黑的。
5）對每個節點，從該節點到其子孫節點的所有路徑上包含相同節點數目的黑節點。

C++代碼實現：
BRTreeNode.h

1. #ifndef BRTREENODE_H_INCLUDED
2. #define BRTREENODE_H_INCLUDED
3. #include<iostream>
4. usingnamespace std;
5. class BRTree;
6. class BRTreeNode
7. {
8. private:
9. friendclass BRTree;
10. int key;
11. bool color;
12. BRTreeNode* left;
13. BRTreeNode* right;
14. BRTreeNode* parent;
15. public:
16. BRTreeNode():key(-1),color(0),left(NULL),right(NULL),parent(NULL){}
17. BRTreeNode(BRTreeNode* node):key(node->key),color(node->color),left(node->left),right(node->right),parent(node->parent)
18. {}
19. BRTreeNode(int num,bool flag):key(num),color(flag),left(NULL),right(NULL),parent(NULL){}
20. ~BRTreeNode()
21. {
23. }
24. int Getkey()
25. {
26. return key;
27. }
28. bool Getcolor()
29. {
30. returnthis->color;
31. }
32. BRTreeNode* GetLeft()
33. {
34. returnthis->left;
35. }
36. BRTreeNode* Getright()
37. {
38. returnthis->right;
39. }
40. BRTreeNode* Getparent()
41. {
42. returnthis->parent;
43. }
44. void Inorder()
45. {
46. if(this!=NULL)
47. {
48. this->left->Inorder();
49. cout<<this->key<<" ";
50. this->right->Inorder();
51. }
52. }
53. void Preorder()
54. {
55. if(this!=NULL)
56. {
57. cout<<this->key<<" ";
58. this->left->Preorder();
59. this->right->Preorder();
60. }
61. }
62. void Postorder()
63. {
64. if(this!=NULL)
65. {
66. this->left->Postorder();
67. this->right->Postorder();
68. cout<<this->key<<" ";
69. }
70. }
72. void MakeEmpty()
73. {
74. if(this!=NULL)
75. {
76. this->left->MakeEmpty();
77. this->right->MakeEmpty();
78. deletethis;
79. }
80. }
81. int GetHeight()
82. {
83. int L,R;
84. if(this==NULL)
85. {
86. return 0;
87. }
88. L=this->left->GetHeight();
89. R=this->right->GetHeight();
90. return 1+(L>R? L:R);
91. }
92. };
95. #endif // BRTREENODE_H_INCLUDED