二叉搜索树（BinarySearchTree）

二叉查找树是每一个几点都满足左孩子小于根，右孩子大于根的数。为查找而生。
1.创建

bool Insert(BSTNode<K,V>*& root,const K& key,const V& v)
    {
        if(root == NULL)
        {
            root = new Node(key,v);
            return true;
        }
        else
        {
            if(key < root->_key)
            {
                Insert(root->_left,key,v);
            }
            if(key > root->_key)
            {
                Insert(root->_right,key,v);
            }
            else
            {
                return false;
            }
        }
    }

2.查找（递归、非递归）

bool Find_R(BSTNode<K,V>*& root,const K& key)//递归实现
    {
        if(root == NULL)
        {
            return false;
        }
        else
        {
            if(key == root->_key)
            {
                return true;
            }
            else if(key > root->_key)
            {
                Find_R(root->_right,key);
            }
            else
            {
                Find_R(root->_left,key);
            }
        }
    }
    bool Find(BSTNode<K,V>*& root,const K& key)//非递归实现
    {
        if(root == NULL)
        {
            return false;
        }
        Node *cur = root;
        while(cur)
        {
            if(key == cur->_key)
            {
                return true;
            }
            if(key < cur->_key)
            {
                cur = cur->_left;
            }
            else
            {
                cur = cur->_right;
            }
        }
        return false;
    }

3.删除（递归、非递归）

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

                if (parent->_left == del)
                {
                    parent->_left = del->_left;
                }
                else
                {
                    parent->_right = del->_left;
                }
                delete del;
                return true;
            }
            else
            {
                Node *InOrderfirst = del->_right;
                Node *parent = del;
                while (InOrderfirst->_left)
                {
                    parent = InOrderfirst;
                    InOrderfirst = InOrderfirst->_left;
                }
                swap(del->_key, InOrderfirst->_key);
                swap(del->_value, InOrderfirst->_value);
                if(InOrderfirst->_right != NULL)
                {
                    parent->_left = InOrderfirst->_left;
                }
                delete InOrderfirst;
                return true;
            }
        }
        return false;
    }
    bool Remove_R(Node*& root, const K& key)
    {
        if (root == NULL)
        {
            return false;
        }
        if (key < root->_key)
        {
            return Remove_R(root->_left, key);
        }
        else if (key > root->_key)
        {
            return Remove_R(root->_right, key);
        }
        else
        {
            Node* del = root;
            if (root->_left == NULL)
            {
                root = del ->_right;
            }
            else if (root->_right == NULL)
            {
                root = del->_left;
            }
            else
            {
                Node* First = root->_right;
                while (First->_left)
                {
                    First = First->_left;
                }
                swap(del->_key, First->_key);
                swap(del->_value, First->_value);
                return Remove_R(root->_right, key);
            }
            delete del;
            del = NULL;
            return true;
        }
    }

4.摧毁

void Destroy(BSTNode<K,V>* root)
        {
            if(root == NULL)
            {
                return;
            }
            Destroy(root->_left);
            Destroy(root->_right);
            if(root->_left == NULL&&root->_right == NULL)
            {
                delete root;
            }
        }