二叉搜索树（BST）的创建、增加、删除、查找。需要注意：BST的左子树必小于根，右子树必大于根，所以不存在值相同的结点。
#include<bits/stdc++.h>
using namespace std;
/*
BST基本操作：
00)递归插入
01)非递归插入
02)调用insert()创建树
03)直接创建树
04)查找
05)删除（用右侧最小值替换被删除的结点）
06)删除（把左子树插入右子树）
*/
/*
BST：
1)是一棵空树
2)具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
特点：
中序周游为递增序列
*/
//BST结点结构
typedef class Node
{
public:
int val;
Node *left;
Node *right;
Node(){ left = right = NULL; }
Node(int tval){ val = tval; left = right = NULL; }
} *BST;
//递归前序周游：
void print_preOrder_recursion(BST root)
{
if(root != NULL)
{
print_preOrder_recursion(root->left);
cout << root->val;
print_preOrder_recursion(root->right);
}
}
/*
递归插入（此结点数据已存在时插入失败，不存在时插入成功）：
遇到空结点时把数据插入；
遇到非空结点时若新数据大于当前结点数据，右下降；小于当前结点时，左下降
*/
bool insert_recursion(BST &root, Node* data)
{
if(root == NULL)
{
root = data;
return true;
}
else{
if(root->val < data->val)
return insert_recursion(root->right, data);
else if(root->val > data->val)
return insert_recursion(root->left, data);
return false;
}
}
/*
非递归插入（此结点数据已存在时插入失败，不存在时插入成功）：
遇到非空结点时若新数据大于当前结点数据，右下降；小于当前结点时，左下降
遇到空结点时把数据插入，需要保留当前父结点，否则数据插不进去。
*/
bool insert_noRecursion(BST root, Node* data)
{
BST pointer = root, last;
int flag;
while(pointer != NULL)
{
last = pointer;
if(pointer->val < data->val)
{
flag = 1;
pointer = pointer->right;
}else if(pointer->val > data->val){
flag = -1;
pointer = pointer->left;
}else
return false;
}
flag > 0 ? last->right = data : last->left = data;
return true;
}
/*
调用insert()创建BST
*/
BST createBST_indirect()
{
int n, val;
cin >> n;
BST root = NULL;
for(int i = 0; i < n; i++)
{
cin >> val;
insert_recursion(root, new Node(val));
}
return root;
}
/*
直接创建BST：
需要保存当前指向结点的父亲结点
*/
BST createBST_direct()
{
int n, i, val, flag = 0;
cin >> n;
if(n <= 0)
return NULL;
cin >> val;
BST root = new Node(val), pointer = NULL, last = NULL;
for(i = 1; i < n; i++)
{
cin >> val;
pointer = root;
while(pointer != NULL)
{
last = pointer;
if(pointer->val < val)
{
flag = 1;
pointer = pointer->right;
}else if(pointer->val > val){
flag = -1;
pointer = pointer->left;
}else{ //此数据已存在时，跳过
flag = 0;
break;
}
}
if(flag == 0)
continue;
flag > 0 ? last->right = new Node(val) : last->left = new Node(val);
}
return root;
}
/*
查找：
周游一遍即可。
*/
bool find(BST root, int val)
{
if(root != NULL)
{
if(root->val == val)
return true;
else if(val < root->val)
return find(root->left, val);
else
return find(root->right, val);
}
return false;
}
/*
删除（不改变总体结构）：
利用 BST中序周游非递减的性质寻找需要删除的结点
用右侧最小结点覆盖被删除的结点，然后删除右侧最小结点
*/
BST delData_noChangeStructure(BST root, int val)
{
if(root == NULL)
return NULL;
if(root->val < val)
root->right = delData_noChangeStructure(root->right, val);
else if(root->val > val)
root->left = delData_noChangeStructure(root->left, val);
else{
if(root->left == NULL || root->right == NULL)
return root->left == NULL ? root->right : root->left;
BST temp = root->right;
while(temp->left != NULL)
temp = temp->left;
root->val = temp->val;
root->right = delData_noChangeStructure(root->right, root->val);
return root;
}
}
/*
删除（改变总体结构）：
利用 BST中序周游非递减的性质寻找需要删除的结点
然后把左子树结点根结点插入右子树
*/
BST delData_changeStructure(BST root, int val)
{
if(root == NULL)
return NULL;
if(root->val < val)
root->right = delData_noChangeStructure(root->right, val);
else if(root->val > val)
root->left = delData_noChangeStructure(root->left, val);
else{
if(root->left == NULL || root->right == NULL)
return root->left == NULL ? root->right : root->left;
insert_noRecursion(root->right, root->left);
root->left = NULL;
root = delData_changeStructure(root, root->val);
return root;
}
}
int main()
{
BST root = createBST_indirect();
insert_recursion(root, new Node(4));
print_preOrder_recursion(root);
cout << endl;
insert_recursion(root, new Node(9));
print_preOrder_recursion(root);
cout << endl;
cout << find(root, 10) << " " << find(root, 4) << endl;
BST del1 = delData_noChangeStructure(root, 2);
print_preOrder_recursion(del1);
cout << endl;
BST del2 = delData_noChangeStructure(root, 3);
print_preOrder_recursion(del1);
return 0;
}
/*
input：
5
2 4 1 3 0
BST：
2
1 4
0 3 9
*/
