#pragma once
#include <iostream>
using namespace std;

template <class T>
class BSTNode
{
public:
    T key;
    BSTNode *parent;
    BSTNode *left;
    BSTNode *right;

    BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value),parent(p),left(l),right(r)
    {

    }
};

template <class T>
class BSTree
{
private:
    BSTNode<T> *mRoot;

public:
    BSTree():mRoot(NULL){}
    ~BSTree(){}

    // 前序排序
    void preOrder()
    {
        preOrder(mRoot);
    }
    void inOrder()
    {
        inOrder(mRoot);
    }
    void postOrder()
    {
        postOrder(mRoot);
    }
    // 查找二叉树中键值为key的节点
    BSTNode<T>* SearchKey(const T key)
    {
        return SearchKey(mRoot, key);
    }
    BSTNode<T>* minKey()
    {
        return minKey(mRoot);
    }
    BSTNode<T>* maxKey()
    {
        return maxKey(mRoot);
    }
    // 插入节点
    void insert( T key)
    {
        BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL);

        if (z == NULL)
        {
            return;
        }
        insert(mRoot, z);
    }

private:
    // 前序排序
    void preOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            cout << tree->key << " ";
            preOrder(tree->left);
            preOrder(tree->right);
        }
    }

    // 中序排序
    void inOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            preOrder(tree->left);
            cout << tree->key << " ";
            preOrder(tree->right);
        }
    }

    // 后序排序
    void postOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            preOrder(tree->left);
            preOrder(tree->right);
            cout << tree->key << " ";
        }
    }
    BSTNode<T>* SearchKey(BSTNode<T>* pNode, const T key) const
    {
        // 递归查找
        /*if (pNode = NULL || key == pNode->key)
        {
            return pNode;
        }
        else if (key > pNode->key)
        {
            return SearchKey(pNode->right);
        }
        else
        {
            return SearchKey(pNode->left);
        }*/

        // 非递归查找
        BSTNode<T>* x = pNode;
        while (x != NULL)
        {
            if (key > x->key)
            {
                x = x->right;
            }
            else if (key < x->key)
            {
                x = x->left;
            }
            else
            {
                return x;
            }
        }

        return NULL;
    }
    // 将节点插入到二叉树中
    void insert(BSTNode<T>* &tree, BSTNode<T> *Node)
    {
        BSTNode<T> *y = NULL;
        BSTNode<T> *x = tree;  
        while (NULL != x)
        {
            y = x;
            if (Node->key > x->key)
            {
                x = x->right;
            }
            else
            {
                x = x->left;
            }
        }

        Node->parent = y;       // 这到后面两句为关键代码
        if (NULL == y)
        {
            tree = Node;
        }
        else if (Node->key > y->key)
        {
            y->right = Node;
        }
        else
        {
            y->left = Node;
        }
    }
    // 查找最小节点
    BSTNode<T>* minKey(BSTNode<T>* pNode) const 
    {
        while (pNode != NULL)
        {
            pNode = pNode->left;
        }

        return pNode;
    }
    BSTNode<T>* maxKey(BSTNode<T>* pNode) const
    {
        while (pNode != NULL)
        {
            pNode = pNode->right;
        }

        return pNode;
    }
    // 找节点（x）的后继节点。即查找二叉树中数值大于该节点的最小值
    BSTNode<T>* Successor(BSTNode<T>* x)
    {
        // 分三种情况
        // 1. x有右孩子，找到以右孩子为根的子树的最小节点
        // 2. x没有右孩子，当x为左孩子，则x的父节点为后继节点
        // 2. x没有右孩子，当x为右孩子，则找x的最低父节点，并且该父节点具有左孩子
        if (x->right != NULL)
        {
            return minKey(x->right);
        }
        BSTNode<T>* y = x->parent;
        while ((NULL != y) &&(x == y->right))
        {
            x= y;
            y = y->parent;
        }

        return y;
    }
    // 找结点(x)的前驱结点。即查找"二叉树中数据值小于该结点"的"最大结点"
    BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
    {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x->left != NULL)
            return maxKey(x->left);

        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T>* y = x->parent;
        while ((y!=NULL) && (x==y->left))
        {
            x = y;
            y = y->parent;
        }

        return y;
    }
                                        
    // 删除二叉树中的节点，并返回被删除的节点
    //BSTNode<T>* RemoveNode(BSTNode<T>* &tree, BSTNode<T>* pNode)
    //{
    //    BSTNode<T>* x = tree;

    //    while (NULL != x && pNode->key != x->key)
    //    {
    //        if (pNode->key > x->key)
    //        {
    //            x = x->right;
    //        }
    //        else if (pNode->key < x->key)
    //        {
    //            x = x->left;
    //        }
    //    }

    //    // 找到或x为空

    //}
};