#include<iostream>

template<class Elem>
class BinNode
{
public:
    virtual Elem& getVal() = 0;
};

template<class Elem>
class BinNodePtr:public BinNode<Elem>
{
public:
    Elem val;
    BinNodePtr* lc;
    BinNodePtr* rc;
    BinNodePtr()
    {
        lc = rc = NULL;
    }
    ~BinNodePtr()
    {
        delete lc;
        delete rc;
    }
    Elem& getVal()
    {
        return this->val;
    }
};

template<class Elem>
class BST
{
public:
    BinNodePtr<Elem> *root;
    int nodenum;
    void midorder(BinNodePtr<Elem>* start);
public:
    BST()
    {
        root = NULL;
        nodenum = 0;
    }
    bool insert(BinNodePtr<Elem>*&ptr,const Elem &e);//
    void remove(BinNodePtr<Elem>*&start,const Elem &e);//
    BinNodePtr<Elem>* getRoot(){return root;}
};

template<class Elem>
void BST<Elem>::midorder(BinNodePtr<Elem> *start)
{
    if(start == NULL) return;
    midorder(start->lc);
    printf("%d ",start->getVal());
    midorder(start->rc);
}

template<class Elem>
bool BST<Elem>::insert(BinNodePtr<Elem>*&ptr,const Elem &e)
{
    if(ptr == NULL)
    {
        ptr = new BinNodePtr<Elem>;
        ptr->lc = NULL;
        ptr->rc = NULL;
        ptr->val = e;
        return true;
    }
    else
    {
        if(ptr->val < e || ptr->val == e)
        {
            insert(ptr->rc,e);
        }
        else
        {
            insert(ptr->lc,e);
        }
    }
    return false;
}

template<class Elem>
void BST<Elem>::remove(BinNodePtr<Elem>*&start,const Elem &e)
{
    if(start == NULL)
        return ;
    if(start->val < e)
        remove(start->rc,e);
    else if(start->val > e)
        remove(start->lc,e);
    else
    {
        if(start->lc == NULL && start->rc == NULL)
        {
            delete start;
        }
        else if(start->lc == NULL)
        {
            BinNodePtr<Elem> *temp = start;
            start = start->rc;
            delete (temp);
        }
        else if(start->rc == NULL)
        {
            BinNodePtr<Elem> *temp = start;
            start = start->lc;
            delete temp;
        }
        else
        {
            BinNodePtr<Elem>* temp = start->rc;
            while(temp->lc!= NULL)
            {
                temp = temp->lc;
            }
            start->val = temp->val;
            remove(start->rc,temp->val);
        }

    }
}
int main()
{
    BST<int> myBST;
    (myBST.insert(myBST.root,10));
    (myBST.insert(myBST.root,20));
    (myBST.insert(myBST.root,5));
    (myBST.insert(myBST.root,30));
    myBST.midorder(myBST.getRoot());
    myBST.remove(myBST.root,10);
    myBST.midorder(myBST.getRoot());
    system("pause");
    return 0;
}