#include<iostream>
using namespace std;

/*
定义树节点，定义树类，中序遍历，二叉搜索树插入，二叉搜索树删除，二叉搜索树析构
*/

template<typename T>
struct TreeNode
{
    T value;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode() : value(T()),left(nullptr),right(nullptr){}
    TreeNode(T x) : value(x),left(nullptr),right(nullptr){}
};

template<typename T>
class searchTree{
    private:
    TreeNode<T>* root;
    TreeNode<T>* removeNode(TreeNode<T>* ptr,T value);
    TreeNode<T>* insertNode(TreeNode<T>* ptr,T value);
    void midOrder(TreeNode<T>* node);
    public:
    searchTree() : root(nullptr){}
    ~searchTree(){
        while(root){
            remove(root->value);
        }
    }
    void remove(T value);
    void insert(T value);
    void midOrderTraversal();
};

//插入，值大插右边，值小插左边
template<typename T>
TreeNode<T>* searchTree<T>::insertNode(TreeNode<T>* node,T value){
    if( node == nullptr){
        return new TreeNode<T>(value);
    }
    if(value > node->value){
        node->right = insertNode(node->right,value);
    }else if(value < node->value)
    {
        node->left = insertNode(node->left,value);
    }
    return node;
}

//删除，从根节点遍历下去，找到点删除，删出之后：叶结点（left,right都为null）：无需任何操作
//其它结点（left = null），（right = null），（letf，right都不为空）
template<typename T>
TreeNode<T>* searchTree<T>::removeNode(TreeNode<T>* node,T value){
    if(node == nullptr){
        cout << "没有这个结点"  << endl;
        return nullptr;
    }
    if(value > node->value){
        node->right = removeNode(node->right,value);
    }
    else if(value < node->value){
        node->left = removeNode(node->left,value);
    }
    else{
        if(node->left == nullptr && node->right == nullptr){
            //该结点是叶结点
            delete node;
            node = nullptr;
            return nullptr;
        }
        else if(node->left == nullptr){
            //只有右子树
            TreeNode<T>* temp = node;
            node = node->right;
            delete temp;
            return node;
        }
        else if(node->right == nullptr){
            //只有左子树
            TreeNode<T>* temp = node;
            node = node->left;
            delete temp;
            return node;
        }
        else{
            TreeNode<T>* temp = node->right;
            while(temp->left != nullptr){
                temp = temp->left;
            }
            node->value = temp->value;
            node->right = removeNode(node->right,temp->value);
            return node;
        }
        
    }
    return node;
}

//中序遍历,递归,基准条件(空结点)
template<typename T>
void searchTree<T>::midOrder(TreeNode<T>* node){
    if(node == nullptr){
        return;
    }else{
        midOrder(node->left);
        cout << node->value;
        midOrder(node->right);
    }
}

template<typename T>
void searchTree<T>::remove(T value){
    root = removeNode(root,value);
}

template<typename T>
void searchTree<T>::insert(T value){
    root = insertNode(root,value);
}

template<typename T>
void searchTree<T>::midOrderTraversal(){
    midOrder(root);
}

int main(){
    searchTree<int> st;
    st.insert(1);
    st.insert(2);
    st.insert(3);
    st.insert(4);
    st.insert(5);
    st.insert(6);
    st.insert(7);
    st.insert(8);
    st.remove(5);
    st.midOrderTraversal();
    return 0;
}