/*
二叉搜索树(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);
}
对于查找一个结点x的后继结点来说，其第二种情况即：如果结点x没有右子树，那么对于x的父结点来说又可以分为两种情况，1）x结点在其父结点的左子树上；2）x结点在其父结点的右子树上。当然我们不可能这样无休止的分析下去，因为相对于x结点的所有祖先来说，x结点所在的位置情况都有两种。若是x结点有n个祖先，那么就会出现2n中情况。所以可以另辟蹊径，那我们从遍历二叉搜索树着手。试想一下，我们可以通过中序遍历一棵二叉搜索树得到一串有序序列。那么对于中序遍历来说，其x结点的后继就是我们要找的点。如果结点x在中序遍历序列中不是最后一个结点的话，那么它必有一个后继结点（线性表的性质）。
好，假如对于一个结点x，其后继结点y存在，那么y->key一定大于x->key。我们可以这样考虑：
根据二叉搜索树的性质，我们知道x的左子树中的任一结点的key值都小于x，所以y必定不在其左子树中。那么结点y必定为x的最先结点或者其祖先结点的右子树。而且y的key值是其中大于x的key值且最小的一个，所以y结点不可能是其祖先的右子树上的 结点。接着我们就可以确定y必定是x的祖先结点，x结点必定在y的左子树中，也就是说y的左孩子也是x的祖先，那么对于所有满足条件的祖先结点有n个（pi-1<pi）其中i = 0,1,...,n-1.由此可以推知，x的后继结点必定为其中最小的一个即p0。得到一个结论：结点x的右子树为空，如果x有一个后继结点y，那么y就是x的有左孩子的最底层祖先，并且它也是x的一个祖先。