map.h
#pragma once
typedef int KEY;
typedef double VALUE;
class CMap
{
    struct SNode
    {
        KEY key;
        VALUE value;
        SNode* pLeft, * pRight;
    };
    SNode* m_pRoot;
    void PostOrder(SNode* p);
    int m_nCount;

public:
    int GetCount() const
    {
        return m_nCount;
    }
    bool IsEmpty() const
    {
        return m_nCount <= 0;
    }

    inline void SetAt(const KEY& key, const VALUE& value)
    {
        (*this)[key] = value;
    }
    bool Lookup(const KEY& key, VALUE& rValue) const;
    //如果找到key，将value地址返回，如果没有找到插入个空的再返回
    VALUE& operator[](const KEY& key);
    inline void RemoveAll()//清理所有节点，用什么方法？三种遍历的哪一种？
    {
        PostOrder(m_pRoot);
    }
    bool RemoveKey(const KEY& key);//二叉树删除稍微有点绕
    CMap() :m_nCount(0), m_pRoot(nullptr)
    {

    }
    ~CMap()
    {
        RemoveAll();
    }
};

// map.cpp
#include "Map.h"

void CMap::PostOrder(SNode* p)
{
   if (p->pLeft)
        PostOrder(p->pLeft);
    if (p->pRight)
        PostOrder(p->pRight);
    delete p;
}

bool CMap::Lookup(const KEY& key, VALUE& rValue) const
{
    SNode* p = m_pRoot;
    while (p)
    {
        if (key == p->key)
            return rValue = p->value,true;
        if (key < p->key)
            p = p->pLeft;
        else
            p = p->pRight;
    }
    return false;
}

// 不用二级指针
VALUE& CMap::operator[](const KEY& key)
{
    SNode* p = m_pRoot, *pRes = nullptr;
    if (!p)
    {
        m_pRoot = new SNode{ key };
        return m_pRoot->value;
    }
    while (true)
    {
        if (p->key == key)
            return p->value;
        if (key < p->key)
        {
            if (p->pLeft)
                p = p->pLeft;
            else
            {
                p->pLeft = new SNode{ key };
                pRes = p->pLeft;
                break;
            }
        }
        else
        {
            if (p->pRight)
                p = p->pRight;
            else
            {
                p->pRight = new SNode{ key };
                pRes = p->pRight;
                break;
            }
        }
    }
    return pRes->value;
}

// 用二级指针操控节点的指针域
VALUE& CMap::operator[](const KEY& key)
{
    auto p = &m_pRoot;
    while (*p)
    {
        if ((*p)->key == key)
            return (*p)->value;
        if (key < (*p)->key)
            p = &(*p)->pLeft;
        else
            p = &(*p)->pRight;
    }
    *p = new SNode{ key };
    return (*p)->value;
}

// 用二级指针操控节点的指针域
bool CMap::RemoveKey(const KEY& key) 
{
    auto p = &m_pRoot; 
    while (*p)
    {
        if ((*p)->key == key)
        {
            auto q = *p;
            *p = q->pRight;
            do
                p = &(*p)->pLeft;
            while (*p);
            *p = q->pLeft;
            delete q;
            return true;
        }
        if (key < (*p)->key)
            p = &(*p)->pLeft;
        else
            p = &(*p)->pRight;
    }
    return false;
}

// test.cpp
#include "Map.h"
#include <iostream>
using namespace std;
CMap m;

void Input()
{
    m[41] = 88.88;
    m[22] = 99.99;
    m[58] = -1;
    m[15] = 66.66;
    m[33] = 11.11;
    m[37] = 55.555;
    m[13] = 777.77;
    m[18] = 2222;
    m[58] = 4444.44;
    m[50] = -234;
    m[69] = -9.99;
    m[66] = -222;
    m[88] = 54321;
    m[53] = -3355;
    m[42] = 4422;

}
void Test(int n)
{
    double d;
    if (m.Lookup(n, d))
        cout << n << "=>" << d << endl;
    else
        cout << "没有 " << n << endl;
}
int main()
{
    Input();
    Test(22);

    m.RemoveKey(22);
    Test(66);
    Test(53);
    Test(54);
    Test(13);
    Test(22);

    m.RemoveKey(41);

    m.RemoveAll();
    return 0;
}