红黑树的定义:
一棵二叉查找树如果满足下面的红黑性质,则为一棵红黑树:
1)每个节点或是红的,或是黑的。
2)根节点是黑的。
3)每个叶节点(NIL)是黑节点。
4)如果一个节点是红的,则它的两个儿子都是黑的。
5)对每个节点,从该节点到其子孙节点的所有路径上包含相同节点数目的黑节点。
C++代码实现:
BRTreeNode.h
- #ifndef BRTREENODE_H_INCLUDED
- #define BRTREENODE_H_INCLUDED
- #include<iostream>
- usingnamespace std;
- class BRTree;
- class BRTreeNode
- {
- private:
- friendclass BRTree;
- int key;
- bool color;
- BRTreeNode* left;
- BRTreeNode* right;
- BRTreeNode* parent;
- public:
- BRTreeNode():key(-1),color(0),left(NULL),right(NULL),parent(NULL){}
- BRTreeNode(BRTreeNode* node):key(node->key),color(node->color),left(node->left),right(node->right),parent(node->parent)
- {}
- BRTreeNode(int num,bool flag):key(num),color(flag),left(NULL),right(NULL),parent(NULL){}
- ~BRTreeNode()
- {
- }
- int Getkey()
- {
- return key;
- }
- bool Getcolor()
- {
- returnthis->color;
- }
- BRTreeNode* GetLeft()
- {
- returnthis->left;
- }
- BRTreeNode* Getright()
- {
- returnthis->right;
- }
- BRTreeNode* Getparent()
- {
- returnthis->parent;
- }
- void Inorder()
- {
- if(this!=NULL)
- {
- this->left->Inorder();
- cout<<this->key<<" ";
- this->right->Inorder();
- }
- }
- void Preorder()
- {
- if(this!=NULL)
- {
- cout<<this->key<<" ";
- this->left->Preorder();
- this->right->Preorder();
- }
- }
- void Postorder()
- {
- if(this!=NULL)
- {
- this->left->Postorder();
- this->right->Postorder();
- cout<<this->key<<" ";
- }
- }
- void MakeEmpty()
- {
- if(this!=NULL)
- {
- this->left->MakeEmpty();
- this->right->MakeEmpty();
- deletethis;
- }
- }
- int GetHeight()
- {
- int L,R;
- if(this==NULL)
- {
- return 0;
- }
- L=this->left->GetHeight();
- R=this->right->GetHeight();
- return 1+(L>R? L:R);
- }
- };
- #endif // BRTREENODE_H_INCLUDED