1、介绍二叉搜索树
二叉搜索树（又称，二叉排序树）的特点：对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。
如图：
根据这个性质，对一个二叉树进行中序遍历，如果是单调递增的，则可以说明这个树是二叉搜索树。
LeetCode题目98:验证二叉搜索树(https://leetcode-cn.com/problems/validate-binary-search-tree/)就可以对这个二叉树进行中序遍历，然后判断是否单调递增的，如果是单调递增的，说明是二叉搜索树。否则不是二叉搜索树。
2、查找操作
二叉搜索树中查找某关键字时，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：
- 如果相等，查找成功；
- 如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
- 如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；
3、插入操作
如果新节点的key在树中已经存在，则把旧节点覆盖；如果没有，则插入。
与查找类似，设新节点的key为X，从根节点开始比较。如果X比根节点大，则去与根节点的右节点比较。如此类推，如果找到了某个节点的key与X相同，覆盖这个节点；如果没找到，则根据最后一次比较结果，插到最后一次比较的节点的左节点或右节点。
4、删除操作
在查找过程中，如果在使用二叉搜索树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉搜索树。
假设要删除的为结点 p，则对于二叉搜索树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：
- 结点 p 为叶子结点，此时只需要删除该结点即可；
- 结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树；
- 结点 p 左右子树都有，此时有两种处理方式：
（1）令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树，如图所示；
（2）用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉搜索树中对其直接前驱（或直接后继）做删除操作。如图为使用直接前驱代替结点 p：
上图中，在对左图进行中序遍历时，得到的结点 p 的直接前驱结点为结点 s，所以直接用结点 s 覆盖结点 p，由于结点 s 还有左孩子，根据第 2 条规则，直接将其变为双亲结点的右孩子。
5、代码实现
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ElemType int
#define KeyType int
/* 二叉排序树的节点结构定义 */
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//二叉排序树查找算法
int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p) {
//如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息
if (!T) {
*p = f;
return FALSE;
}
//如果相等，令 p 指针指向该关键字，并返回查找成功信息
else if (key == T->data) {
*p = T;
return TRUE;
}
//如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树
else if (key < T->data) {
return SearchBST(T->lchild, key, T, p);
}
else {
return SearchBST(T->rchild, key, T, p);
}
}
int InsertBST(BiTree *T, ElemType e) {
BiTree p = NULL;
//如果查找不成功，需做插入操作
if (!SearchBST((*T), e, NULL, &p)) {
//初始化插入结点
BiTree s = (BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
//如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点
if (!p) {
*T = s;
}
//如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
else if (e < p->data) {
p->lchild = s;
}
else {
p->rchild = s;
}
return TRUE;
}
//如果查找成功，不需要做插入操作，插入失败
return FALSE;
}
//删除函数
int Delete(BiTree *p)
{
BiTree q, s;
//情况 1，结点 p 本身为叶子结点，直接删除即可
if (!(*p)->lchild && !(*p)->rchild) {
*p = NULL;
}
else if (!(*p)->lchild) { //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
q = *p;
*p = (*p)->rchild;
free(q);
}
else if (!(*p)->rchild) {//右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
q = *p;
*p = (*p)->lchild;//这里不是指针 *p 指向左子树，而是将左子树存储的结点的地址赋值给指针变量 p
free(q);
}
else {//左右子树均不为空，采用第 2 种方式
q = *p;
s = (*p)->lchild;
//遍历，找到结点 p 的直接前驱
while (s->rchild)
{
q = s;
s = s->rchild;
}
//直接改变结点 p 的值
(*p)->data = s->data;
//判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
if (q != *p) {
q->rchild = s->lchild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
}
else {
q->lchild = s->lchild;//否则，直接将左子树上移即可
}
free(s);
}
return TRUE;
}
int DeleteBST(BiTree *T, int key)
{
if (!(*T)) {//不存在关键字等于key的数据元素
return FALSE;
}
else
{
if (key == (*T)->data) {
Delete(T);
return TRUE;
}
else if (key < (*T)->data) {
//使用递归的方式
return DeleteBST(&(*T)->lchild, key);
}
else {
return DeleteBST(&(*T)->rchild, key);
}
}
}
void order(BiTree t)//中序输出
{
if (t == NULL) {
return;
}
order(t->lchild);
printf("%d ", t->data);
order(t->rchild);
}
int main()
{
int i;
int a[5] = { 3,4,2,5,9 };
BiTree T = NULL;
for (i = 0; i < 5; i++) {
InsertBST(&T, a[i]);
}
printf("中序遍历二叉排序树：
");
order(T);
printf("
");
printf("删除3后，中序遍历二叉排序树：
");
DeleteBST(&T, 3);
order(T);
}
中序遍历二叉排序树：
2 3 4 5 9
删除3后，中序遍历二叉排序树：
2 4 5 9
6、其他操作
作者——MichaelCen——二叉搜索树的其他操作还包括：查找最大值、最小值；给定一个key，寻找最接近它的节点；给定一个key X,求有多少个节点的key比X小等等可以参考一下这个博客。