二叉排序树的c++实现，查找，删除等-白红宇

二叉排序树的c++实现，查找，删除等

阅读量：4186 次

发布时间：2019-05-26

本文共 1906 字，大约阅读时间需要 6 分钟。

二叉排序树的c++实现

完整代码和测试在我的github:

#pragma oncetemplate 
   
    struct BSTNode{    T m_nValue;    BSTNode *m_pLeft;    BSTNode *m_pRight;};template 
    
     class BST{public:    BST(T r[],int n);    void InsertBST(BSTNode
     
       *&R, BSTNode
      
        *s);//插入数据在BST,R根结点，插入结点s    BSTNode
       
         *Search(BSTNode
        
          *r, T key); bool DeleteBST(BSTNode
         
          *&R, T key);//删除key void Delete(BSTNode
          
           *&R); BSTNode
           
             * GetpRoot();private: BSTNode 
            
              *root;};template 
             
              void BST
              
               ::InsertBST(BSTNode
               
                 *&R, BSTNode
                
                  *s){ if (R == nullptr) R = s;//R为空，将s直接插入 else if (s->m_nValue < R->m_nValue) InsertBST(R->m_pLeft, s);//递归向左子树中插入 else InsertBST(R->m_pRight, s);}//构造BST的过程即是一个反复插入的过程template 
                 
                  BST
                  
                   ::BST(T r[], int n){ root = nullptr; for (size_t i = 0; i < n; i++) { BSTNode
                   
                     *s = new BSTNode
                    
                     ; s->m_nValue = r[i]; s->m_pLeft= nullptr; s->m_pRight = nullptr; InsertBST(root, s);//插入 }}template 
                     
                      BSTNode
                      
                       * BST
                       
                        ::Search(BSTNode
                        
                          *r, T key){ if (r == nullptr) return nullptr; if (key == r->m_nValue) return r; else if (r->m_nValue > key) return Search(r->m_pLeft, key); else return Search(r->m_pRight, key);}template 
                         
                          bool BST
                          
                           ::DeleteBST(BSTNode
                           
                            *&R, T key){ if (R == nullptr) return false; else if (R->m_nValue == key) { Delete(R); return true; } else if (key < R->m_nValue) return DeleteBST(R->m_pLeft, key);//查找key值 else return DeleteBST(R->m_pRight, key);}//删除情况分为三种情况//仔细理解template 
                            
                             void BST
                             
                              ::Delete(BSTNode
                              
                               *&R){ BSTNode
                               
                                *q, *s; if (R->m_pLeft==nullptr)//如果其左子树为空 { q = R; R = R->m_pRight;//R的右子数赋给R delete q;//删除q,即以前的R } if (R->m_pRight==nullptr) { q = R; R = R->m_pLeft; delete q; } else//左右子数都在 { q = R; s = R->m_pLeft; //寻找最大值进行与根结点的替换 while (s->m_pRight!=nullptr) { q = s; s = s->m_pRight; } R->m_nValue = s->m_nValue;//将此最大值赋给要删除的节点 if (q != R)//即进行了while循环，改变q q->m_pRight = s->m_pLeft;//s是q的右孩子，s是没有右子数的 else R->m_pLeft = s->m_pLeft; delete s; }}//获得根指针template 
                                
                                  BSTNode
                                 
                                   * BST
                                  
                                    ::GetpRoot(){ return root;}