#ifndef __BSTREE_H__
#define __BSTREE_H__
/*
参考：http://www.cnblogs.com/skywang12345/p/3576373.html

这里是介绍二叉查找树

1）若任意结点的左子树不空，则左子树上所有的结点的值均小于它的根结点的值
2）若任意结点的右子树不空，则左子树上所有的结点的值均大于它的根结点的值
3）任意结点的左右子树也分别为二叉查找树
4）没有键值相等的结点（但是这里实现的可以有相同key值的结点）。当键值相同时，插入在右子树中。
*/
#include<iomanip>
#include<iostream>
using namespace std;

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

    BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value), parent(p),left(l), right(r)
    {
        //cout << "BSTNode() +++ " << endl;
    }
};

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

public:
    BSTree();
    ~BSTree();

    void insert(T key);
    void print();
    void preOrder();
    T maximum();
    T minimum();
    int remove(T data);
    void destory();
    
private:
    void insert(BSTNode<T> *&tree, BSTNode<T> *z);
    void print(BSTNode<T> *tree, T key, int direction);
    void preOrder(BSTNode<T> *tree) const;
    BSTNode<T>*  maximum(BSTNode<T> *tree);
    BSTNode<T>*  minimum(BSTNode<T> *tree);
    BSTNode<T>* getNode(T data);
    void destory(BSTNode<T> *tree);
};


template <class T>
BSTree<T>::BSTree()
{
    mRoot = NULL;
}

template <class T>
BSTree<T>::~BSTree()
{

}

template <class T>
void BSTree<T>::insert(T key)
{
    BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL);
    if(z)
    {
        insert(mRoot, z);
    }
}

// 这里的&是引用传递
template <class T>
void BSTree<T>::insert(BSTNode<T> *&tree, BSTNode<T> *pNode) 
{
    BSTNode<T> *pIndex = NULL;
    BSTNode<T> *pTemp = tree;

    // 先找到插入的位置
    while(pTemp != NULL)
    {
        pIndex = pTemp;
        if(pNode->key < pTemp->key)
            pTemp = pTemp->left;
        else
            pTemp = pTemp->right;
    }

    pNode->parent = pIndex;
    if(!pIndex)
        tree  = pNode;
    else if(pNode->key < pIndex->key)
        pIndex->left = pNode;
    else
        pIndex->right = pNode;

}



template <class T>
void BSTree<T>::print()
{
    if(mRoot)
    {
        print(mRoot, mRoot->key, 0);
    }
}

/*
key:结点的键值
direction：
    -1 - 表示为左孩子
    0 - 表示为根节点
    1 - 表示为左孩子
*/
template <class T>
void BSTree<T>::print(BSTNode<T> *tree, T key, int direction)
{
    if(tree)
    {
        if(direction == 0)
            cout << setw(2) << tree->key << " is root" << endl;
        else
            cout << setw(2) << tree->key << " is " << setw(2) << key << "'s " << setw(12) << (direction==1?"right child":"left child") << endl;

        print(tree->left, tree->key, -1);
        print(tree->right, tree->key, 1);
    }
}

template <class T>
void BSTree<T>::preOrder()
{
    cout << "preOrder: ";
    preOrder(mRoot);
    cout << endl;
}


// 这里是遍历。
template <class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
    if(tree)
    {
        #if 1 // 前置遍历
        cout << tree->key << " "; 
        preOrder(tree->left);
        preOrder(tree->right);
        #endif
        
        #if 0 // 中序遍历
        preOrder(tree->left);
        cout << tree->key << " ";     
        preOrder(tree->right);
        #endif

        #if 0 // 后序遍历
        preOrder(tree->left);    
        preOrder(tree->right);
        cout << tree->key << " ";     
        #endif
    }
}

// 找二叉查找树中的最大值，返回key值最大的那个结点
template <class T>
BSTNode<T> * BSTree<T>::maximum(BSTNode<T> *tree)
{
    BSTNode<T> *temp = tree;
    if(temp)
    {
        while(temp->right)
        {
            temp = temp->right;
        }

        return temp;
    }
    else
    {
        return NULL;
    }
}


// 找二叉查找树中的最小值，返回key值最小的那个结点
template <class T>
BSTNode<T> * BSTree<T>::minimum(BSTNode<T> *tree)
{
    BSTNode<T> *temp = tree;
    if(temp)
    {
        while(temp->left)
        {
            temp = temp->left;
        }

        return temp;
    }
    else
    {
        return NULL;
    }
}

template <class T>
T BSTree<T>::maximum()
{
    BSTNode<T> *temp = maximum(mRoot);
    if(temp)
    {
        return temp->key;
    }

    return NULL;
}

template <class T>
T BSTree<T>::minimum()
{
    BSTNode<T> *temp = minimum(mRoot);
    if(temp)
    {
        return temp->key;
    }

    return NULL;
}

// 通过data去获取结点。
template <class T>
BSTNode<T>* BSTree<T>::getNode(T data)
{
    BSTNode<T> *temp = mRoot;
    if(!temp)
    {
        return NULL;
    }

    while(temp)
    {
        if(temp->key == data)
            return temp;
        else if(temp->key < data)
            temp = temp->right;
        else
            temp = temp->left;
    }

    return NULL;
}


// 这个仅仅是用来打印结点的。测试用的
template <class T>
void showNode(BSTNode<T>* node)
{
        if(node->parent)
        {
            cout << "    parent: " << node->parent->key << endl;
        }
        else
        {
            cout << "    parent is NULL" << endl;
        }

        if(node->left)
        {
            cout << "    left: " << node->left->key << endl;
        }
        else
        {
            cout << "    left is NULL" << endl;
        }

        if(node->right)
        {
            cout << "    right: " << node->right->key << endl;
        }
        else
        {
            cout << "    right is NULL" << endl;
        }
}

/*
参考：http://blog.csdn.net/zq17865815296/article/details/52658908
先说一下如何删除二叉树查找树的节点吧。总共有三种情况
1.被删除的节点是叶子节点，这时候只要把这个节点删除，再把指向这个节点的父节点指针置为空就行
2.被删除的节点有左子树，或者有右子树，而且只有其中一个，那么只要把当前删除节点的父节点指向被删除节点的左子树或者右子树就行。
3.被删除的节点既有左子树而且又有右子树，这时候需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置，为什么要这样呢，
根据二叉查找树的性质，父节点的指针一定比所有左子树的节点值大而且比右子树的节点的值小，为了删除父节点不破坏二叉查找树的平衡性，
应当把左子树最大的节点或者右子树最小的节点放在父节点的位置，这样的话才能维护二叉查找树的平衡性。（我是找的右子树的最小节点）
*/
template <class T>
int BSTree<T>::remove(T data)
{
    cout << "remove :" << data << endl;
    BSTNode<T>* node = getNode(data);// 这里要找到要删除的结点。
    if(node)
    {
        showNode(node);
        if(node->parent == NULL)// 删除根结点
        {
            // 这里选择的是把左子树接到右子树中key最小的那个结点的左结点上。还有一种是把右子树接到左子树的key最大的那个右结点上
            BSTNode<T> *temp = minimum(node->right);
            if(temp)
            {
                temp->left = node->left;
                mRoot = node->right;// 要更新根节点
            }
            delete node;
            node = NULL;
            return 0;
        }

        if((node->right == NULL) && (node->left == NULL)) // 删除叶子结点
        {
            if(node->parent->left == node)
            {
                node->parent->left = NULL;
            }
            else
            {
                node->parent->right = NULL;
            }
        }
        else if(node->right && node->left) // 删除有两个子节点的
        {
            BSTNode<T> *temp = minimum(node->right); // 获取后继结点，这个结点一定是没有左子树的。
            cout << "have left and right child, mimmum :" << temp->key << endl;
            if(temp == temp->parent->left) // 后继结点如果是左结点，就将它的右子树接到它父亲的左子树中。
            {
                temp->parent->left = temp->right;
            }
            else // 后继结点如果是右结点，就将它的右子树接到它父亲的右子树中。
            {
                temp->parent->right = temp->right;
            }
            node->key = temp->key; // 把后继结点的key保存在要删除的结点中
            delete temp; // 其实是删除的后继结点。
            temp = NULL;
        }
        else // 删除只有一个只有一个子结点。
        {
            if(node->right) // 有右子节点
            {
                if(node->parent->left == node)
                {
                    node->parent->left = node->right;
                }
                else
                {
                    node->parent->right = node->right;
                }
            }
            else
            {
                if(node->parent->left == node)
                {
                    node->parent->left = node->left;
                }
                else
                {
                    node->parent->right = node->left;
                }    
            }        
            delete node;
            node = NULL;
        }

    }
    else
    {
        return -1;
    }

    return 0;
}


template <class T>
void BSTree<T>::destory(BSTNode<T> *tree)
{
    if(tree)
    {
        if(tree->left)
            destory(tree->left);
        if(tree->right)
            destory(tree->right);
        delete tree;
        tree = NULL;
    }
}

template <class T>
void BSTree<T>::destory()
{
    destory(mRoot);
}

#endif // __BSTREE_H__

#include<iostream>
#include"bstree.h"
using namespace std;

/*
可以插入相同的，会插入在右子树中。
*/
void fun()
{
    cout << "fun() +++ " << endl;
    int i = 0, len = 0;
    BSTree<int>* tree = new BSTree<int>;
    if(tree->mRoot == NULL)
        cout << "fun() mRoot is NULL" << endl;
    int arr[] = {2, 15, 4, 44, 30, 36, 50, 12, 55, 414};
    int count = sizeof(arr)/sizeof(int);
    for(int i = 0; i<count; i++)
    {
        tree->insert(arr[i]);
    }
    tree->insert(125);

    tree->insert(5);
    tree->preOrder();
    int maxkey = tree->maximum();
    cout << "Max key = " << maxkey << endl;
    int minkey = tree->minimum();
    cout << "Min key = " << minkey << endl;
    tree->remove(12);
    tree->remove(2);

    tree->preOrder();
    //tree->print();

    tree->destory();
    cout << "fun() --- " << endl;
}

int main()
{
    cout << "hello world" << endl;
    fun();
    return 0;
}