//BST.h
#pragma once
template <typename T> class BST;
template <typename T> class BSTNode {
public:
    friend class BST<T>;
    BSTNode() {
        lChild = rChild = parent = nullptr;
        data = nullptr;
    }
    BSTNode(T value) {
        lChild = rChild = parent = nullptr;
        data = value;
    }
private:
    BSTNode<T>* lChild, * rChild, * parent;
    T data;
};

template<typename T> class BST {
public:
    BST() { }

    //插入操作
    void insert(BSTNode<T>* node);

    //二叉查找树的中序遍历，就相当于排序了
    void inSort(BSTNode<T>* node);

    //按节点删除
    void deleteNode(BSTNode<T>* node);

    //按数值删除
    void deleteNode(const T& t);

    BSTNode<T>* search(T key);
    BSTNode<T>* root = nullptr;

private:
    int count;
};

template<typename T>
void BST<T>::insert(BSTNode<T>* node)
{
    BSTNode<T>* curr, * temp = nullptr;
    curr = root;
    while (nullptr != curr) //遍历二叉树，找到应该插入的父节点
    {
        temp = curr;
        if (node->data > curr->data)
        {
            curr = curr->rChild;
        }
        else {
            curr = curr->lChild;
        }
    }
    node->parent = temp;//temp 代码当前最后遍历的node，设置node->parent为该节点
    if (temp == nullptr)
    {
        root = node;
        count++;
    }
    else {
        if (node->data < temp->data)
        {
            temp->lChild = node;
            count++;
        }
        else {
            temp->rChild = node;
            count++;
        }
    }
}

template<typename T>
void BST<T>::inSort(BSTNode<T>* node)
{
    if (node != nullptr)
    {
        inSort(node->lChild);
        std::cout << node->data << ",";
        inSort(node->rChild);
    }
}

template<typename T>
inline void BST<T>::deleteNode(BSTNode<T>* node)
{
    BSTNode<T>* p = node->parent;//获取node的父节点，这里很重要
    if (node->lChild == nullptr && node->rChild == nullptr) //叶子节点直接删除
    {
        if (node == node->parent->lChild)
        {
            node->parent->lChild = nullptr;
        }
        else {
            node->parent->rChild = nullptr;
        }
        delete node;
        count--;
    }
    else if (node->rChild != nullptr && node->lChild == nullptr) {//存在右孩子
        if (p == nullptr)//说明节点为根节点
        {
            root = node->rChild;
            count--;
        }
        else {
            node->rChild->parent = p;
            if (p->lChild == node) //判断是父节点的左孩子还是右孩子
            {
                p->lChild = node->rChild;
            }
            else {
                p->rChild = node->rChild;
            }
            delete node;
            count--;
        }
    }
    else if (node->lChild != nullptr && node->rChild == nullptr)//存在左孩子
    {
        if (p == nullptr)
        {
            root = root->lChild;
            count--;
        }
        else {
            node->lChild->parent = p;
            if (p->lChild == node)
            {
                p->lChild = node->lChild;
            }
            else {
                p->rChild = node->lChild;
            }
            delete node;
            count--;
        }
    }
    else {
        BSTNode<T>* left, * curp = nullptr;
        left = node->rChild; //本方案是找右侧最小值，替换node节点，其他节点保持不动即可
        while (left != nullptr)
        {
            curp = left;
            left = left->lChild;
        }

        if (curp->rChild != nullptr)
        {
            if (curp->lChild == curp)
            {
                curp->parent->lChild = curp->rChild;
            }
            else {
                curp->parent->rChild = curp->rChild;
            }
        }
        else {
            if (curp->parent->lChild == curp)
            {
                curp->parent->lChild = nullptr;
            }
            else {
                curp->parent->rChild = nullptr;
            }
            //curp->parent->lChild = nullptr;
        }
        //替curp 替换 node
        curp->parent = p;
        curp->lChild = node->lChild;
        curp->rChild = node->rChild;

        if (p->lChild == node)//判断node 是p 的左孩子还是右孩
        {
            p->lChild = curp;
        }
        else {
            p->rChild = curp;
        }
        delete node;
        count--;
    }
}

template<typename T>
inline void BST<T>::deleteNode(const T& k)
{
    BSTNode<T>* node = search(k);
    if (node != nullptr)
    {
        deleteNode(node);
    }
}


template<typename T>
inline BSTNode<T>* BST<T>::search(T k)
{
    BSTNode<T>* node = root;
    while (node != nullptr)
    {
        if (k < node->data)
        {
            node = node->lChild;
        }
        else if (k > node->data)
        {
            node = node->rChild;
        }
        else {
            break;
        }
    }
    return node;
}

//BSTree.h

//BST.cpp
#include "BST.h"

//main.cpp
//https://www.cnblogs.com/clc2008/p/10193550.html
//#include "pch.h"
#include <iostream>
#include "BST.h"
using namespace std;

int main()
{
    // 树结构示意
    //     30
    //    /  \
    //  15   25
    // /  \
    //9    18
    //   /   \
    //  16   25
    //      /  \
    //    20    26  
    BST<int> sbt;
    sbt.insert(new BSTNode<int>(30));
    sbt.insert(new BSTNode<int>(15));
    sbt.insert(new BSTNode<int>(9));
    sbt.insert(new BSTNode<int>(18));
    sbt.insert(new BSTNode<int>(16));
    sbt.insert(new BSTNode<int>(25));
    sbt.insert(new BSTNode<int>(20));
    sbt.insert(new BSTNode<int>(26));
    sbt.insert(new BSTNode<int>(35));

    cout << "搜索树排序后:";
    sbt.inSort(sbt.root);

    sbt.deleteNode(18);

    cout << endl << "删除18 后排序:";

    sbt.inSort(sbt.root);
}