【高阶数据结构】深度探索二叉树进阶：二叉搜索树概念及其高效实现（三）

#pragma once
#include <string>
template<class K>
    struct  BSTreeNode
    {
        BSTreeNode(const K& key = K())
            :_left(nullptr)
                , _right(nullptr)
                , _key(key)
            {}
        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;
    };
template<class K>
    class  BSTree
    {
        public:
        typedef BSTreeNode<K> Node;
        //插入操作
        bool Insert(const K& key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            Node* parent = nullptr;
            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;
                }
            }
            cur = new Node(key);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else if (parent->_key > key)
            {
                parent->_left = cur;
            }
            return true;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            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
                {
                    //找到位置
                    //删除
                    //先判断谁为空
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else if (parent->_right == cur)
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (parent->_left == cur)
                            {
                                parent->_right = cur->_left;
                            }
                            else if (parent->_right == cur)
                            {
                                parent->_left = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    //替换法实现
                    else
                    {
                        Node* RightMinParent = cur;
                        Node* RightMin = cur->_right;
                        //找到右子树最大的值
                        while (RightMin->_left)
                        {
                            RightMinParent = RightMin;
                            RightMin = RightMin->_left;
                        }
                        //找到
                        swap(cur->_key, RightMin->_key);
                        if (RightMinParent->_left == RightMin)
                        {
                            RightMinParent->_left = RightMin->_right;
                        }
                        else
                        {
                            RightMinParent->_right = RightMin->_right;
                        }
                        delete RightMin;
                    }
                    return true;
                }
            }
            return false;
        }
        bool Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
        private:
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
        private:
        Node* _root = nullptr;
    };