代码可以根据《红黑树研究记录-实例》那篇文章的图来验证

main.cpp

#include 
     
      #include "RBTree.h"using namespace std;int main(int argc, char *argv[]){    int arr[20] = {
   12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17};    RBTree *tree = new RBTree();    for(int i = 0; i < 20; i++)        tree->InsertNode(arr[i]);            std::cout<<"PreOrder:"<
      
       PreOrder();    std::cout<<"InOrder:"<
       
        InOrder();    std::cout<<"PostOrder:"<
        
         PostOrder();        std::cout<
         
          <<"Delete Node:"<
          
           DeleteNode(12); tree->PreOrder(); cout<<"Delete 1:"<
           
            DeleteNode(1); tree->PreOrder(); cout<<"Delete 9:"<
            
             DeleteNode(9); tree->PreOrder(); cout<<"Delete 2:"<
             
              DeleteNode(2); tree->PreOrder(); cout<<"Delete 0:"<
              
               DeleteNode(0); tree->PreOrder(); cout<<"Delete 11:"<
               
                DeleteNode(11); tree->PreOrder(); cout<<"Delete 7:"<
                
                 DeleteNode(7); tree->PreOrder(); cout<<"Delete 19:"<
                 
                  DeleteNode(19); tree->PreOrder(); cout<<"Delete 4:"<
                  
                   DeleteNode(4); tree->PreOrder(); cout<<"Delete 15:"<
                   
                    DeleteNode(15); tree->PreOrder(); cout<<"Delete 18:"<
                    
                     DeleteNode(18); tree->PreOrder(); cout<<"Delete 5:"<
                     
                      DeleteNode(5); tree->PreOrder(); cout<<"Delete 14:"<
                      
                       DeleteNode(14); tree->PreOrder(); cout<<"Delete 13:"<
                       
                        DeleteNode(13); tree->PreOrder(); cout<<"Delete 10:"<
                        
                         DeleteNode(10); tree->PreOrder(); cout<<"Delete 6:"<
                         
                          DeleteNode(6); tree->PreOrder(); cout<<"Delete 16:"<
                          
                           DeleteNode(16); tree->PreOrder(); cout<<"Delete 3:"<
                           
                            DeleteNode(3); tree->PreOrder(); cout<<"Delete 8:"<
                            
                             DeleteNode(8); tree->PreOrder(); cout<<"Delete 17:"<
                             
                              DeleteNode(17); tree->PreOrder(); return 0;}
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

RBTree.h

#ifndef _RBTREE_HEADER_#define _RBTREE_HEADER_#include 
     
      #include 
      
       #include 
       
        enum NodeColor{    RED,    BLACK};struct RBNode{    int value;    NodeColor color;    RBNode *pParent;    RBNode *pLeft;    RBNode *pRight;};class RBTree{public:    RBTree();    ~RBTree();        int InsertNode(int);    int DeleteNode(int);    RBNode *FindNode(int value);        void PreOrder();    void InOrder();    void PostOrder();private:    void DeleteAll();    void TurnLeft(RBNode *pNode);    void TurnRight(RBNode *pNode);    int DeleteNode(RBNode *);    RBNode *GetSuccessor(RBNode *);    int InsertNode(RBNode *);    void DeleteFixup(RBNode *);    void InsertFixup(RBNode *);private:    RBNode *m_root;};#endif
       
      
     

RBTree.cpp

#include "RBTree.h"#include 
     
      #include 
      
       using namespace std;RBTree::RBTree(){    m_root = NULL;}RBTree::~RBTree(){    DeleteAll();}void RBTree::TurnLeft(RBNode *pNode){    if(!pNode || !pNode->pParent)        return;    RBNode *pp = pNode->pParent->pParent;    if(pp)        if(pp->pLeft == pNode->pParent)            pp->pLeft = pNode;        else            pp->pRight = pNode;    pNode->pParent->pParent = pNode;    pNode->pParent->pRight = pNode->pLeft;    if(pNode->pLeft)        pNode->pLeft->pParent = pNode->pParent;    pNode->pLeft = pNode->pParent;        pNode->pParent = pp;    }void RBTree::TurnRight(RBNode *pNode){    if(!pNode || !pNode->pParent)        return;    RBNode *pp = pNode->pParent->pParent;    if(pp)        if(pp->pLeft == pNode->pParent)            pp->pLeft = pNode;        else            pp->pRight = pNode;    pNode->pParent->pParent = pNode;    pNode->pParent->pLeft = pNode->pRight;    if(pNode->pRight)        pNode->pRight->pParent = pNode->pParent;    pNode->pRight = pNode->pParent;        pNode->pParent = pp;}void RBTree::DeleteAll(){    if(!m_root)        std::cout<<"The tree is null"<
       
         qu;    qu.push(m_root);    while(qu.size() > 0)    {        RBNode *pCur = qu.front();        qu.pop();        std::cout<<"Delete:"<
        
         value<<"("<
         
          color<<"), "<
          
           pLeft) qu.push(pCur->pLeft); if(pCur->pRight) qu.push(pCur->pRight); delete pCur; pCur = NULL; }}int RBTree::InsertNode(int value){ if(FindNode(value)) return -1; RBNode *pNew = new RBNode(); pNew->value = value; pNew->pParent = NULL; pNew->color = RED; pNew->pLeft = NULL; pNew->pRight = NULL; return InsertNode(pNew);}int RBTree::InsertNode(RBNode* pNode){ if(!pNode) return -1; if(!m_root) { m_root = pNode; m_root->color = BLACK; return 0; } RBNode *tmp = m_root; RBNode *tmpParent = NULL; while(tmp) { tmpParent = tmp; if(tmp->value > pNode->value) tmp = tmp->pLeft; else tmp = tmp->pRight; } if(tmpParent->value > pNode->value) tmpParent->pLeft = pNode; else tmpParent->pRight = pNode; pNode->pParent = tmpParent; InsertFixup(pNode);}void RBTree::InsertFixup(RBNode *pNode){ if(!pNode) return; RBNode *pUncle = NULL; while(pNode->pParent && pNode->pParent->color == RED) { if(pNode->pParent == pNode->pParent->pParent->pLeft) { pUncle = pNode->pParent->pParent->pRight; if(pUncle && pUncle->color == RED) //case 1 { pNode->pParent->color = BLACK; pUncle->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else { if(pNode == pNode->pParent->pRight) //case 2 { TurnLeft(pNode); pNode = pNode->pLeft; } pNode->pParent->color = BLACK; //case 3 pNode->pParent->pParent->color = RED; TurnRight(pNode->pParent); if(!pNode->pParent->pParent) m_root = pNode->pParent; } } else { pUncle = pNode->pParent->pParent->pLeft; if(pUncle && pUncle->color == RED) //case 1 { pNode->pParent->color = BLACK; pUncle->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else { if(pNode == pNode->pParent->pLeft) //case 2 { TurnRight(pNode); pNode = pNode->pRight; } pNode->pParent->color = BLACK; //case 3 pNode->pParent->pParent->color = RED; TurnLeft(pNode->pParent); if(!pNode->pParent->pParent) m_root = pNode->pParent; } } } m_root->color = BLACK;}int RBTree::DeleteNode(int value){ RBNode *pNode = NULL; if(!(pNode = FindNode(value))) return -1; return DeleteNode(pNode);}RBNode *RBTree::GetSuccessor(RBNode *pNode){ RBNode *pThis = pNode->pRight; while(pThis->pLeft) pThis = pThis->pLeft; return pThis;}int RBTree::DeleteNode(RBNode *pNode){ if(!pNode) return -1; RBNode *pDel = NULL; RBNode *pThis = NULL; //search the Node if(!pNode->pLeft && !pNode->pRight) { pThis = pNode; pDel = pNode; } else if(!pNode->pLeft || !pNode->pRight) pDel = pNode; else pDel = GetSuccessor(pNode); //delete the Node if(pDel->pLeft) pThis = pDel->pLeft; else if(pDel->pRight) pThis = pDel->pRight; else pThis = pDel; if(pThis != pDel) { pThis->pParent = pDel->pParent; if(!pDel->pParent) m_root = pThis; else if(pDel == pDel->pParent->pLeft) pDel->pParent->pLeft = pThis; else pDel->pParent->pRight = pThis; } if(pDel != pNode) pNode->value = pDel->value; if(pDel->color == BLACK) DeleteFixup(pThis); if(pThis == pDel) if(pDel == pDel->pParent->pLeft) pDel->pParent->pLeft = NULL; else pDel->pParent->pRight = NULL; if(pDel == m_root) m_root = NULL; delete pDel; pDel = NULL;}void RBTree::DeleteFixup(RBNode *pNode){ RBNode *pBrother = NULL; while(pNode != m_root && pNode->color == BLACK) { if(pNode == pNode->pParent->pLeft) { pBrother = pNode->pParent->pRight; if(pBrother->color == RED) //case 1 { pBrother->color = BLACK; pNode->pParent->color = RED; TurnLeft(pBrother); pBrother = pNode->pParent->pRight; } if((!pBrother->pLeft || pBrother->pLeft->color == BLACK) && (!pBrother->pRight || pBrother->pRight->color == BLACK)) //case 2 { pBrother->color = RED; pNode = pNode->pParent; } else { if(!pBrother->pRight || pBrother->pRight->color == BLACK) //case 3 { pBrother->pLeft->color = BLACK; pBrother->color = RED; TurnRight(pBrother->pLeft); pBrother = pNode->pParent->pRight; } pBrother->color = pNode->pParent->color; //case 4 pNode->pParent->color = BLACK; pBrother->pRight->color = BLACK; TurnLeft(pBrother); pNode = m_root; } } else { pBrother = pNode->pParent->pLeft; if(pBrother->color == RED) //case 1 { pBrother->color = BLACK; pNode->pParent->color = RED; TurnRight(pBrother); pBrother = pNode->pParent->pLeft; } if((!pBrother->pLeft || pBrother->pLeft->color == BLACK) && (!pBrother->pRight || pBrother->pRight->color == BLACK)) //case 2 { pBrother->color = RED; pNode = pNode->pParent; } else { if(!pBrother->pLeft || pBrother->pLeft->color == BLACK) //case 3 { pBrother->pRight->color = BLACK; pBrother->color = RED; TurnLeft(pBrother->pRight); pBrother = pNode->pParent->pLeft; } pBrother->color = pNode->pParent->color; pNode->pParent->color = BLACK; pBrother->pLeft->color = BLACK; TurnRight(pBrother); pNode = m_root; } } } pNode->color = BLACK;}RBNode *RBTree::FindNode(int value){ if(!m_root) return NULL; RBNode *tmp = m_root; while(tmp) { if(value > tmp->value) tmp = tmp->pRight; else if(value < tmp->value) tmp = tmp->pLeft; else break; } return tmp;}void RBTree::PreOrder(){ if(!m_root) { std::cout<<"The tree is null"<
           
             qu; qu.push(m_root); while(qu.size() > 0) { RBNode *pCur = qu.front(); qu.pop(); std::cout<
            
             value<<"("<
             
              color<<"), "; if(pCur->pLeft) qu.push(pCur->pLeft); if(pCur->pRight) qu.push(pCur->pRight); } std::cout<
              
                de; RBNode *pCur = m_root; bool bPush = false; while(pCur) { if(pCur->pLeft && !bPush) { de.push_back(pCur); pCur = pCur->pLeft; continue; } std::cout<
               
                value<<"("<
                
                 color<<"), "; if(pCur->pRight) { pCur = pCur->pRight; bPush = false; } else { if(de.size() == 0) break; pCur = de.back(); de.pop_back(); bPush = true; } } std::cout<
                 
                   de; int flag = 0; RBNode *pCur = m_root; while(pCur) { if(pCur->pLeft && flag < 1) { de.push_back(pCur); pCur = pCur->pLeft; continue; } if(pCur->pRight && flag < 2) { de.push_back(pCur); pCur = pCur->pRight; flag = 0; continue; } std::cout<
                  
                   value<<"("<
                   
                    color<<"), "; if(de.size() == 0) break; RBNode *pParent = de.back(); de.pop_back(); if(pCur == pParent->pLeft) { flag = 1; pCur = pParent; } else if(pCur == pParent->pRight) { flag = 2; pCur = pParent; } } std::cout<