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

红黑树的定义：

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

1）每个节点或是红的，或是黑的。

2）根节点是黑的。

3）每个叶节点（NIL）是黑节点。

4）如果一个节点是红的，则它的两个儿子都是黑的。

5）对每个节点，从该节点到其子孙节点的所有路径上包含相同节点数目的黑节点。

C++代码实现：

BRTreeNode.h

[cpp]
<SPAN style="FONT-SIZE: 14px">#ifndef BRTREENODE_H_INCLUDED
#define BRTREENODE_H_INCLUDED
#include<iostream>
using namespace std;
class BRTree;
class BRTreeNode
{
private:
    friend class 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()
    {
        return this->color;
    }
    BRTreeNode* GetLeft()
    {
        return this->left;
    }
    BRTreeNode* Getright()
    {
        return this->right;
    }
    BRTreeNode* Getparent()
    {
        return this->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();
            delete this;
        }
    }
    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
</SPAN>

#ifndef BRTREENODE_H_INCLUDED
#define BRTREENODE_H_INCLUDED
#include<iostream>
using namespace std;
class BRTree;
class BRTreeNode
{
private:
friend class 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()
{
  return this->color;
}
BRTreeNode* GetLeft()
{
  return this->left;
}
BRTreeNode* Getright()
{
  return this->right;
}
BRTreeNode* Getparent()
{
  return this->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();

补充：软件开发 , C++ ,