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

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;

void InOrder()
{
    _InOrder(_root);
    cout << endl;
}
private:
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

// 改造二叉搜索树为KV结构
template<class K, class V>
    struct BSTNode
    {
        BSTNode(const K& key = K(), const V& value = V())
            : _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value)
            {}
        BSTNode<T>* _pLeft;
        BSTNode<T>* _pRight;
        K _key;
        V _value
    };
template<class K, class V>
    class BSTree
    {
        typedef BSTNode<K, V> Node;
        typedef Node* PNode;
        public:
        BSTree(): _pRoot(nullptr){}
        PNode Find(const K& key);
        bool Insert(const K& key, const V& value)
            bool Erase(const K& key)
            private:
        PNode _pRoot;
    };
void TestBSTree3()
{
    // 输入单词，查找单词对应的中文翻译
    BSTree<string, string> dict;
    dict.Insert("string", "字符串");
    dict.Insert("tree", "树");
    dict.Insert("left", "左边、剩余");
    dict.Insert("right", "右边");
    dict.Insert("sort", "排序");
    // 插入词库中所有单词
    string str;
    while (cin>>str)
    {
        BSTreeNode<string, string>* ret = dict.Find(str);
        if (ret == nullptr)
        {
            cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;
        }
        else
        {
            cout << str << "中文翻译:" << ret->_value << endl;
        }
    }
}
void TestBSTree4()
{
    // 统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
                    "苹果", "香蕉", "苹果", "香蕉" };
    BSTree<string, int> countTree;
    for (const auto& str : arr)
    {
        // 先查找水果在不在搜索树中
        // 1、不在，说明水果第一次出现，则插入<水果, 1>
        // 2、在，则查找到的节点中水果对应的次数++
        //BSTreeNode<string, int>* ret = countTree.Find(str);
        auto ret = countTree.Find(str);
        if (ret == NULL)
        {
            countTree.Insert(str, 1);
        }
        else
        {
            ret->_value++;
        }
    }
    countTree.InOrder();
}