搜索二叉树的基本操作

川长思鸟来 2022-06-15 07:12 248阅读 0赞

![这里写图片描述][SouthEast]  
搜索二叉树的非递归基本操作

为什么要找右孩子的最左节点
    因为右孩子的最左节点一定比要删除的节点的右孩子上的任意一个节点都要小替换删除之后搜索为茶树还是搜索二叉树
    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    template<class K>
    struct BinarySearchTreeNode
    {
             BinarySearchTreeNode<K > *_left;
             BinarySearchTreeNode<K > *_right;
             K _key;
            BinarySearchTreeNode( const K &x)
                   :_left( NULL)
                   , _right( NULL)
                   , _key( x)
            {
    
            }
    };
    template<class K>
    class BinarySearchTree
    {
             typedef BinarySearchTreeNode <K> Node;
    public:
            BinarySearchTree()
                   :_root( NULL)
            {
    
            }
        bool BinarySearchInsert( const K & key)
            {
                    if (_root == NULL )
                   {
                           _root = new Node (key);
                            return true ;
                   }
                    else
                   {
                            Node *cur = _root;
                            Node *parent = NULL ;
                            while (cur)
                           {
                                   if (cur->_key > key )
                                  {
                                          parent = cur;
                                          cur = cur->_left;
                                  }
                                   else if (cur->_key < key)
                                  {
                                          parent = cur;
                                          cur = cur->_right;
                                  }
                                   else
                                  {
                                           return false ;
                                  }
                           }
                            if (key >parent->_key)
                           {
                                  parent->_right = new Node (key);
                                   return true ;
                           }
                            else if (key < parent->_key)
                           {
                                  parent->_left = new Node (key);
                                   return true ;
                           }
                   }
            }
             const Node * Find(const K&key )
            {
                    if (_root == NULL )
                   {
                            return NULL ;
                   }
                    else
                   {
                            Node*cur = _root;
                            while (cur)
                           {
                                   if (cur->_key > key )
                                  {
                                          cur = cur->_left;
                                  }
                                   else if (cur->_key < key)
                                  {
                                          cur = cur->_right;
                                  }
                                   else
                                  {
                                           return cur;
                                  }
                           }
                            return NULL ;
                   }
            }
             bool Remove(const K& key)
            {
                    if (_root == NULL )
                   {
                            return false ;
                   }
                    else
                   {
                            Node*del = NULL ;
                            Node*cur = _root;
                            Node*parent = NULL ;
                            while (cur)
                           {
                                   if (cur->_key > key )
                                  {
                                          parent = cur;
                                          cur = cur->_left;
                                  }
                                   else if (cur->_key < key)
                                  {
                                          parent = cur;
                                          cur = cur->_right;
                                  }
                                   else
                                  {
                                           if (cur->_left == NULL )
                                          {
                                                  if (parent->_left == cur)
                                                 {
                                                         del = cur;
                                                         parent->_left = cur->_right;
                                                 }
                                                  else
                                                 {
                                                         del = cur;
                                                         parent->_right = cur->_right;
                                                 }
                                          }
                                           else if (cur->_right == NULL)
                                          {
                                                  if (parent->_left == cur)
                                                 {
                                                         del = cur;
                                                         parent->_left = cur->_left;
                                                 }
                                                  else
                                                 {
                                                         del = cur;
                                                         parent->_right = cur->_left;
                                                 }
                                          }
                                           else//要删除的节点左右都不为空，使用替换法
                                          {
                                                  Node *parent = cur;
                                                  Node*subRight = cur->_right;//选择找右孩子的最左节点
                                                  while (subRight->_left)
                                                 {
                                                         parent = subRight;
                                                         subRight = subRight->_left;
                                                 } 
                                                 cur->_key = subRight->_key;
                                                  if (parent->_left == subRight)
                                                 {
                                                         del = cur;
                                                         parent->_left = subRight->_left;
                                                 }
                                                  else
                                                 {
                                                         del = cur;
                                                         parent->_right = subRight->_left;
                                                 }
                                          }
                                  }
                                   delete del;
                                  del = NULL;
                                   return true ;
                           }
                            return false ;
                   }
            }
             void InOrder()
            {
                   _InOrder(_root);
            }
    protected:
             void _InOrder(Node *root)
            {
                    if (root == NULL)
                   {
                            return;
                   }
                   _InOrder( root->_left);
                   cout << root->_key << " " ;
                   _InOrder( root->_right);
            }
             Node*_root;
    };
    int main()
    {
             BinarySearchTree<int >bs;
            bs.BinarySearchInsert(5);
            bs.BinarySearchInsert(3);
            bs.BinarySearchInsert(4);
            bs.BinarySearchInsert(1);
            bs.BinarySearchInsert(7);
            bs.BinarySearchInsert(8);
            bs.BinarySearchInsert(2);
            bs.BinarySearchInsert(6);
            bs.BinarySearchInsert(0);
            bs.BinarySearchInsert(9);
            bs.InOrder();
            cout << endl;
            bs.Remove(5);
            bs.Remove(3);
            bs.Remove(4);
            bs.Remove(1);
            bs.InOrder();
            system( "pause");
             return 0;
    }

搜索二叉树递归的基本操作

搜索二叉树递归的基本操作
    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    template <class K>
    struct BinarySearchTreeNode
    {
             BinarySearchTreeNode <K > *_left;
             BinarySearchTreeNode <K > *_right;
             K _key;
            BinarySearchTreeNode( const K & x)
                   :_left( NULL )
                   , _right( NULL )
                   , _key( x )
            {
    
            }
    };
    template <class T>
    class BinarySearchTree
    {
             typedef BinarySearchTreeNode < T> Node ;
    public :
            BinarySearchTree()
                   :_root( NULL )
            {
    
            }
             bool BinarySearchInsertR(const T& key )
            {
                    return _InsertR(_root, key );
            }
             Node *Find(const T& key )
            {
                    return _Find(_root, key );
            }
             bool Remove(const T& key )
            {
                    return _Remove(_root, key );
            }
             void InOrder()
            {
                   _InOrder(_root);
                   cout << endl;
            }
    protected :
             void _InOrder(Node * root)
            {
                    if (root == NULL)
                   {
                            return ;
                   }
                   _InOrder( root ->_left);
                   cout << root ->_key << " " ;
                   _InOrder( root ->_right);
            }
             bool _InsertR(Node *& root, const T & key)
            {
                    if (root == NULL)
                   {
                            root = new Node( key );
                            return true ;
                   }
                    if (root ->_key > key)
                   {
                            return _InsertR(root ->_left, key);
                   }
                    else if ( root->_key < key )
                   {
                            return _InsertR(root ->_right, key);
                   }
                    else
                   {
                            return false ;
                   }
            }
             Node * _Find(Node * root, const T & key)
            {
                    if (root == NULL)
                   {
                            return NULL ;
                   }
                    if (root ->_key < key)
                   {
                            return _Find(root ->_right, key);
                   }
                    else if ( root->_key> key )
                   {
                            return _Find(root ->_left, key);
                   }
                    else
                   {
                            return root ;
                   }
            }
             bool _Remove(Node *& root, const T & key)
            {
                    if (root == NULL)
                   {
                            return false ;
                   }
                    if (root ->_key < key)
                   {
                            return _Remove(root ->_right, key);
                   }
                    else if ( root->_key> key )
                   {
                            return _Remove(root ->_left, key);
                   }
                    else //找到了可以删除
                   {
                            Node *del = NULL ;
                            if (root ->_left == NULL)
                           {
                                  del = root ;
                                   root = root ->_right;
                                   return true ;
                           }
                            else if ( root->_right == NULL )
                           {
                                  del = root ;
                                   root = root ->_left;
                           }
                            else //左右子树都不为空,找到右子树的最左节点
                           {
                                   Node *left = root ->_right;
                                   while (left->_left)
                                  {
                                          left = left->_left;
                                  }
                                   root ->_key = left->_key;
                                  _Remove( root ->_right, left->_key);
                               return true ;
                           }
                   }
            }
             Node *_root;
    };
    int main()
    {
             BinarySearchTree <int >bs;
            bs.BinarySearchInsertR(5);
            bs.BinarySearchInsertR(3);
            bs.BinarySearchInsertR(4);
            bs.BinarySearchInsertR(1);
            bs.BinarySearchInsertR(7);
            bs.BinarySearchInsertR(8);
            bs.BinarySearchInsertR(2);
            bs.BinarySearchInsertR(6);
            bs.BinarySearchInsertR(0);
            bs.BinarySearchInsertR(9);
            bs.Remove(5);
            bs.Remove(3);
            bs.Remove(4);
            bs.Remove(1);
            bs.Remove(7);
            bs.Remove(8);
            bs.Remove(2);
            bs.Remove(6);
            bs.Remove(0);
            bs.Remove(9);
            bs.InOrder();
            cout << bs.Find(2);
            system( "pause" );
             return 0;
    }

[SouthEast]: /images/20220615/2fa37f5de64046728ada6c9086283e9b.png