算法导论-红黑树C++实现

qizongshuai 2012-11-10

红黑树的定义:

一棵二叉查找树如果满足下面的红黑性质,则为一棵红黑树:

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. {
  22. }
  23. int Getkey()
  24. {
  25. return key;
  26. }
  27. bool Getcolor()
  28. {
  29. returnthis->color;
  30. }
  31. BRTreeNode* GetLeft()
  32. {
  33. returnthis->left;
  34. }
  35. BRTreeNode* Getright()
  36. {
  37. returnthis->right;
  38. }
  39. BRTreeNode* Getparent()
  40. {
  41. returnthis->parent;
  42. }
  43. void Inorder()
  44. {
  45. if(this!=NULL)
  46. {
  47. this->left->Inorder();
  48. cout<<this->key<<" ";
  49. this->right->Inorder();
  50. }
  51. }
  52. void Preorder()
  53. {
  54. if(this!=NULL)
  55. {
  56. cout<<this->key<<" ";
  57. this->left->Preorder();
  58. this->right->Preorder();
  59. }
  60. }
  61. void Postorder()
  62. {
  63. if(this!=NULL)
  64. {
  65. this->left->Postorder();
  66. this->right->Postorder();
  67. cout<<this->key<<" ";
  68. }
  69. }
  70. void MakeEmpty()
  71. {
  72. if(this!=NULL)
  73. {
  74. this->left->MakeEmpty();
  75. this->right->MakeEmpty();
  76. deletethis;
  77. }
  78. }
  79. int GetHeight()
  80. {
  81. int L,R;
  82. if(this==NULL)
  83. {
  84. return 0;
  85. }
  86. L=this->left->GetHeight();
  87. R=this->right->GetHeight();
  88. return 1+(L>R? L:R);
  89. }
  90. };
  91. #endif // BRTREENODE_H_INCLUDED

相关推荐