简介
二叉搜索树（\(Binary\ Search\ Tree\)），简称\(BST\)，用于在一个集合中查找元素。
性质
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
具体操作
1、插入
操作内容：
将一个元素插入二叉搜索树。
操作方法：
将一个元素插入一个二叉搜索树，需要将插入元素与当前节点元素进行比较：
若插入元素等于当前节点元素，则说明已插入过该元素，退出函数。
若插入元素小于当前节点元素，如果当前节点左子树为空，则将该节点左子树定为当前插入元素，否则，继续对当前节点的左子树进行操作。
类似的，若插入元素大于当前节点元素，如果当前节点右子树为空，则将该节点右子树定为当前插入元素，否则，继续对当前节点的右子树进行操作。
代码如下：
void Insert(BST *&x,int v)
{
if(!x)//若当前节点为空
{
x=new BST;//新建一个节点
x->Left=x->Right=NULL,x->num=v;//将这个新节点设定为插入元素
return;
}
if(v==x->num) return;//若已插入过，则退出函数
if(v<x->num) Insert(x->Left,v);//若插入元素小于当前节点元素，则继续对当前节点的左子树进行操作
else Insert(x->Right,v);//反之，继续对当前节点的右子树进行操作
}
2、查询
操作内容：
查询一个元素是否在二叉搜索树中。
操作方法：
查询一个元素是否在二叉搜索树中，需要将查询元素与当前节点元素进行比较：
若查询元素等于当前节点元素，则返回1。
若查询元素小于当前节点元素，如果当前节点左子树为空，则返回0，否则，继续对当前节点的左子树进行操作。
类似的，若查询元素大于当前节点元素，如果当前节点右子树为空，则返回0，否则，继续对当前节点的右子树进行操作。
代码如下：
int Query(BST *x,int v)
{
if(!x) return 0;//若当前节点为空，则返回0
if(v==x->num) return 1;//若查询元素与当前节点相等，则返回1
return v<x->num?Query(x->Left,v):Query(x->Right,v);
}
3、删除
操作内容：
删除二叉搜索树中的一个元素。
操作方法：
删除二叉搜索树中的一个元素，需要将删除元素与当前节点元素进行比较：
若删除元素等于当前节点元素，如果当前节点无子树，则将当前节点设置为空，否则，将当前节点设置为当前节点的一个子树，操作完后退出函数。
若删除元素小于当前节点元素，如果当前节点左子树为空，则退出函数，否则，继续对当前节点的左子树进行操作。
类似的，若删除元素大于当前节点元素，如果当前节点右子树为空，则退出函数，否则，继续对当前节点的右子树进行操作。
具体代码如下：
void Delete(BST *&x,int v)
{
if(!x) return;//若当前节点为空，则退出函数
if(v==x->num) {x->Left->Right=x->Right,x=x->Left;return;}//删除当前节点
if(v<x->num) Delete(x->Left,v);
else Delete(x->Right,v);
}
完整代码
#include<bits/stdc++.h>
#define N 1000
using namespace std;
int Q;
struct BST
{
BST *Left,*Right;
int num;
}*rt=NULL;
void Insert(BST *&x,int v)
{
if(!x)//若当前节点为空
{
x=new BST;//新建一个节点
x->Left=x->Right=NULL,x->num=v;//将这个新节点设定为插入元素
return;
}
if(v==x->num) return;//若已插入过，则退出函数
if(v<x->num) Insert(x->Left,v);//若插入元素小于当前节点元素，则继续对当前节点的左子树进行操作
else Insert(x->Right,v);//反之，继续对当前节点的右子树进行操作
}
int Query(BST *x,int v)
{
if(!x) return 0;//若当前节点为空，则返回0
if(v==x->num) return 1;//若查询元素与当前节点相等，则返回1
return v<x->num?Query(x->Left,v):Query(x->Right,v);
}
void Delete(BST *&x,int v)
{
if(!x) return;//若当前节点为空，则退出函数
if(v==x->num) {x->Left->Right=x->Right,x=x->Left;return;}//删除当前节点
if(v<x->num) Delete(x->Left,v);
else Delete(x->Right,v);
}
int main()
{
scanf("%d",&Q);
for(int i=1;i<=Q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==1) Insert(rt,y);
if(x==2) printf("%d\n",Query(rt,y));
if(x==3) Delete(rt,y);
}
return 0;
}