/*

二叉搜索树(Binary Search Tree)，(又:二叉查找树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

*/
// BinarySearchTree.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

struct BinarySearchTreeNode{

    int key;

    BinarySearchTreeNode *parent;

    BinarySearchTreeNode *left;

    BinarySearchTreeNode *right;

};

struct BinarySearchTree{

    BinarySearchTreeNode *root;

    int nodes;

};

void initeTree(BinarySearchTree &T)

{

    T.root = nullptr;

    T.nodes = ;

}

void allocateNodeSpace(BinarySearchTreeNode **node)

{

    *node = (BinarySearchTreeNode *)malloc(sizeof(BinarySearchTreeNode));

    if (*node == NULL)

        cout << "allocte space error!"<<endl;

    else

    {

        (*node)->left = nullptr;

        (*node)->right = nullptr;

        (*node)->parent = nullptr;

        (*node)->key = ;

    }

}

void inorderVisit(BinarySearchTreeNode *node)

{

    if (node != nullptr)

    {

        inorderVisit(node->left);

        cout << node->key << ' ';

        inorderVisit(node->right);

    }

}

//递归实现

BinarySearchTreeNode &searchOneNode(BinarySearchTreeNode* node,int key)

{

    if (node == nullptr || node->key == key)

        return *node;

    if (node->key < key)

        return searchOneNode(node->right, key);

    else

        return searchOneNode(node->left,key);

}

//迭代实现

BinarySearchTreeNode &searchOneNode1(BinarySearchTreeNode* node, int key)

{

    while (node != nullptr && key != node->key)

    {

        if (node->key < key)

            node = node->right;

        else

            node = node->left;

    }

    return *node;

}

//查找某个结点子树中的最小元素

BinarySearchTreeNode &findMinmum(BinarySearchTreeNode *node)

{

    while (node->left != nullptr)

    {

        node = node->left;

    }

    return *node;

}

//查找某个结点子树中的最大元素

BinarySearchTreeNode &findMaxmum(BinarySearchTreeNode *node)

{

    while (node->right != nullptr)

    {

        node = node->right;

    }

    return *node;

}

//获取一个结点的后继

//两种情况：

//1 结点x的右子树非空，那么x的后继结点恰是x的右子树中的最左结点。

//2 结点x的右子树为空，如果x有一个后继结点y，那么y就是x的有左孩子的最底层祖先，并且它也是x的一个祖先。

BinarySearchTreeNode &getNodeSuccessor(BinarySearchTreeNode *node)

{

    BinarySearchTreeNode *ptr = nullptr;

    ptr = node->right;

    while (ptr != nullptr && ptr->left != nullptr)

    {

        ptr = ptr->left;

    }

    if (ptr == nullptr)

        ptr = node->parent;

    return *ptr;

}

//建立一棵二叉搜索树，即向二叉搜索树中增加结点

void inserTreeNode(BinarySearchTree &T,BinarySearchTreeNode *node)

{

    BinarySearchTreeNode *parentPtr = nullptr;

    BinarySearchTreeNode *temPtr = T.root;

    while (temPtr != nullptr)

    {

        parentPtr = temPtr;

        if (node->key < temPtr->key)

            temPtr = temPtr->left;

        else

            temPtr = temPtr->right;

    }

    node->parent = parentPtr;

    if (parentPtr == nullptr)

        T.root = node;

    else if (node->key < parentPtr->key)

        parentPtr->left = node;

    else

        parentPtr->right = node;

}

//建立一棵二叉搜索树，即

void createTree(BinarySearchTree &T)

{

    int key = -;

    BinarySearchTreeNode *temNode = nullptr;

    while (cin>>key,key!=-)

    {

        allocateNodeSpace(&temNode);

        temNode->key = key;

        inserTreeNode(T,temNode);

    }

}

//用一棵子树v替换另一棵子树u并成为其（u）双亲的孩子结点。

void transplantUV(BinarySearchTree &T,BinarySearchTreeNode *u, BinarySearchTreeNode *v)

{

    if (u->parent == nullptr)

        T.root = v;

    else if (u == u->parent->left)

        u->parent->left = v;

    else

        u->parent->right = v;

    if (v != nullptr)

        v->parent = u->parent;

}

//从二叉搜索树中删除一个结点

/*

从一棵二叉搜索树中删除一个结点node，可以分为三种情况：

1）如果node没有孩子结点，那么可以直接删除该结点；

2）如果node只有一个孩子结点，那么就让该孩子结点取代node的位置；

3）如果node有两个孩子结点，那么找到node的后继结点afterNode（一定在node的右子树中），并让afterNode取代node的位置。

并让node原来的右子树成为afterNode新的右子树，node的左子树成为afterNode的左子树。

对于情况3）又可以分为两种情况：

3.1）afterNode是node的右孩子，那么直接让afterNode取代node的位置，不做其它变换。

3.2）afterNode是node的右子树中的左子树的一个结点，但不是node的右孩子，那么先让afterNode的右孩子取代afterNode的位置，

然后让afterNode取代node的位置，并让node的右子树成为afterNode新的右子树。

*/

void deleteTreeNode(BinarySearchTree &T, int key)

{

    BinarySearchTreeNode *node = &searchOneNode1(T.root,key);

    if (node->left == nullptr)

        transplantUV(T, node, node->right);

    else if (node->right == nullptr)

        transplantUV(T,node,node->left);

    else

    {

        BinarySearchTreeNode *temPtr = &findMinmum(node->right);

        if (temPtr->parent != node)

        {

            transplantUV(T,temPtr,temPtr->right);

            temPtr->right = node->right;

            temPtr->right->parent = temPtr;

        }

        transplantUV(T, node, temPtr);

        temPtr->left = node->left;

        node->left->parent = temPtr;

    }

    free(node);

}

void main(void)

{

    cout << "1.首先构建一棵二叉搜索树:" << endl;

    BinarySearchTree T;

    initeTree(T);

    createTree(T);

    cout << "2.中序遍历二叉搜索树:" << endl;

    inorderVisit(T.root);

//cout << endl;

    //cout << "3.输入出一个结点的后继结点:" << endl;

    //cout << "请输入要查找的结点的关键字Key:" << endl;

    //int keyValue;

    //cin >> keyValue;

    //BinarySearchTreeNode *temPtr = &searchOneNode1(T.root,keyValue);

    //BinarySearchTreeNode *successorPtr = &getNodeSuccessor(temPtr);

    //cout << successorPtr->key;

    //cout << "请输入要删除的结点的关键字:" << endl;

    //cin >> keyValue;

    int keyValue;

    cin >> keyValue;

    deleteTreeNode(T, keyValue);

    inorderVisit(T.root);

}