搜索树

定义

二叉搜索树（Binary Search Tree）， 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

组成

template 
    
      struct BSNode {
       BSNode
     
      * _left;     BSNode
      
       * _right;     K _key;     BSNode
       
        (const K& key)         :_left(NULL)         ,_right(NULL)         ,_key(key)     {} };
       
      
     
    

左右孩子_left,_right,用来比较大小的key值

主要实现操作

插入

当前节点为空，则直接给_root根节点插入。 
比根节点大，插入到根节点的右树上。 
比根节点小，插入到根节点的左树上。

插入代码

bool Insert(const K& key)     {
           if (NULL == _root)         {
               _root = new Node(key);             return true;         }         Node* parent = NULL;         Node* cur = _root;         while (cur)         {
               if (cur->_key < key)             {
                   parent = cur;                 cur = cur->_right;             }             else if(cur->_key > key)             {
                   parent = cur;                 cur = cur->_left;             }             else             {
                   return false;             }         }         if (parent->_key < key)         {
               parent->_right = new Node(key);         }         else         {
               parent->_left = new Node(key);         }         return true;     }

删除

递归版

比当前节点大，到当前节点的右树上查找并删除； 
比当前节点大，到当前节点的右树上查找并删除； 
当前节点就是需要删除的节点 
1.找到当前节点右子树的最左节点，与要被删除节点交换，从当前节点的父节点继续递归删除。

bool _RemoveR(Node*& cur, const K& key)     {
           if (NULL == cur){
               return false;         }         if (cur->_key < key){
               return _RemoveR(cur->_right, key);         }         else if (cur->_key > key){
               return _RemoveR(cur->_left, key);         }         else{
               //找到为key的节点cur             Node* del = cur;             if (NULL == cur->_left){
                   cur = cur->_right;             }             else if (NULL == cur->_right){
                   cur = cur->_left;             }             else             {
                   Node* tmp = cur;                 Node* parent = cur->_right;                 cur = cur->_left;                 while (cur)                 {
                       parent = cur;                     cur = cur->_left;                 }                 //parent现在是以被删除节点为根，右子树的最左节点                 swap(parent->_key, tmp->_key);                 return _RemoveR(parent, key);             }             delete del;             return true;         }         return false;     }

非递归版

找到需要删除的节点，进行如下判断 
1.del（需要删除的节点）的左孩子为空时,判断del是否为根节点，不是根节点，再判断是parent的左孩子还是右孩子,判断好后进行删除 
2.del的右孩子为空时与左类似 
3.del的左右孩子都不为空，使用替换法

bool Rmove(const K& key)     {
           if (NULL == _root){
   return true;}         Node* cur = _root;         Node* parent = NULL;         Node* del = NULL;         while (cur)         {
               if (cur->_key < key)             {
                   parent = cur;                 cur = cur->_right;             }             else if (cur->_key > key)             {
                   parent = cur;                 cur = cur->_left;             }             else             {
                   if (NULL == cur->_left) //删除节点的左孩子为空                 {
                       if (NULL == parent) //当前节点为根节点                     {
                           _root = cur->_right;                     }                     else                     {
                           if (cur == parent->_left)                         {
                               parent->_left = cur->_right;    //让父节点的左孩子指向当前节点的右孩子                                              }                         else if (cur == parent->_right)                         {
                               parent->_right = cur->_right;   //让父节点的右孩子指向当前节点的右孩子                         }                     }                     del = cur;                 }                 else if (NULL == cur->_right)    //删除节点的右孩子为空                 {
                       if (NULL == parent) //当前节点为根节点                     {
                           _root = cur->_left;                     }                     else                     {
                           if (cur == parent->_left)   //parent的左孩子是cur且cur的右孩子为空                         {
                               parent->_left = cur->_left;                         }                         if (cur == parent->_right)                         {
                               parent->_right = cur->_left;//parent的右孩子是cur且cur的右孩子为空                         }                     }                     delete cur;                 }                 else    //删除节点的左右孩子都不为空                 {
                       //利用替换法，将当前节点视为根节点，找当前节点右子树最左节点，与要删除的节点做替换                     Node* tmp = cur;                     Node* subNode = cur->_right;//右子树肯定不为空                     while (subNode->_left)                     {
                           tmp = subNode;                         subNode = subNode->_left;                     }                     //找到右子树的最左节点tmp;                     swap(cur->_key, subNode->_key);//交换数据                     //分两种情况                     if (tmp->_left == subNode)  //tmp的左为替换节点                      {
                           tmp->_left = subNode->_right;                     }                     else if(tmp->_right == subNode)                                             {
                           tmp->_right = subNode->_right;                     }                     del = subNode;                 }                 delete del;                 return true;             }         }         return false;     }

完整实现

BSTree.h

#ifndef __BSTREE_H__ #define __BSTREE_H__ #include 
    
      using namespace std; template 
     
       struct BSNode {
       BSNode
      
       * _left;     BSNode
       
        * _right;     K _key;     BSNode
        
         (const K& key)         :_left(NULL)         ,_right(NULL)         ,_key(key)     {} }; template 
         
           class BSTree { typedef BSNode
          
            Node; public: BSTree() :_root(NULL) {} /*BSTree(const) {}*/ bool Insert(const K& key) { if (NULL == _root) { _root = new Node(key); return true; } Node* parent = NULL; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if(cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } if (parent->_key < key) { parent->_right = new Node(key); } else { parent->_left = new Node(key); } return true; } bool Rmove(const K& key) { if (NULL == _root){ return true;} Node* cur = _root; Node* parent = NULL; Node* del = NULL; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { if (NULL == cur->_left) //删除节点的左孩子为空 { if (NULL == parent) //当前节点为根节点 { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; //让父节点的左孩子指向当前节点的右孩子 } else if (cur == parent->_right) { parent->_right = cur->_right; //让父节点的右孩子指向当前节点的右孩子 } } del = cur; } else if (NULL == cur->_right) //删除节点的右孩子为空 { if (NULL == parent) //当前节点为根节点 { _root = cur->_left; } else { if (cur == parent->_left) //parent的左孩子是cur且cur的右孩子为空 { parent->_left = cur->_left; } if (cur == parent->_right) { parent->_right = cur->_left;//parent的右孩子是cur且cur的右孩子为空 } } delete cur; } else //删除节点的左右孩子都不为空 { //利用替换法，将当前节点视为根节点，找当前节点右子树最左节点，与要删除的节点做替换 Node* tmp = cur; Node* subNode = cur->_right;//右子树肯定不为空 while (subNode->_left) { tmp = subNode; subNode = subNode->_left; } //找到右子树的最左节点tmp; swap(cur->_key, subNode->_key);//交换数据 //分两种情况 if (tmp->_left == subNode) //tmp的左为替换节点 { tmp->_left = subNode->_right; } else if(tmp->_right == subNode) { tmp->_right = subNode->_right; } del = subNode; } delete del; return true; } } return false; } void InOder() { _InOder(_root); cout<
           
            _key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; } bool FindR(const K& key) { return _FindR(_root, key); } ~BSTree() { _Destory(_root); } protected: bool _RemoveR(Node*& cur, const K& key) { if (NULL == cur){ return false; } if (cur->_key < key){ return _RemoveR(cur->_right, key); } else if (cur->_key > key){ return _RemoveR(cur->_left, key); } else{ //找到为key的节点cur Node* del = cur; if (NULL == cur->_left){ cur = cur->_right; } else if (NULL == cur->_right){ cur = cur->_left; } else { Node* tmp = cur; Node* parent = cur->_right; cur = cur->_left; while (cur) { parent = cur; cur = cur->_left; } //parent现在是以被删除节点为根，右子树的最左节点 swap(parent->_key, tmp->_key); return _RemoveR(parent, key); } delete del; return true; } return false; } bool _InsertR(Node*& root, const K& key) { if (NULL == root) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if (root->_key > key) { return _InsertR(root->_left, key); } else return false; } bool _FindR(Node* root,const K& key) { if (NULL == root){ return false;} if (root->_key < key){ return _FindR(root->_right, key); } else if (root->_key > key){ return _FindR(root->_left, key); } else { return true; } return false; } void _Destory(Node* root) { if (NULL == root){ return;} _Destory(root->_left); _Destory(root->_right); delete root; } void _InOder(Node* root) { if (NULL == root){ return;} _InOder(root->_left); cout<
            
             _key<<" "; _InOder(root->_right); } protected: Node* _root; }; #endif //__BSTREE_H__