本文介绍了二叉排序树最基本的三种操作查找，插入和删除。
1 查找
#include<bits/stdc++.h>
using namespace std;
typedef int dataType;
typedef struct BitNode
{
dataType data;
struct BitNode *lChild, *rChild;
}BitNode, *BitTree;
int SearchBST(BitTree t, int key)
{
if (t == NULL)
{
return 0;
}
else
{
if (t->data == key)
{
return 1;
}
else if (t->data > key)
{
return SearchBST(t->lChild, key);
}
else
{
return SearchBST(t->rChild, key);
}
}
}代码中也给出了二叉排序树的结构代码，查找比较简单，就是递归查找，就不说了。
2 插入
int InsertBST(BitTree &T, int key)
{
if (T == NULL)
{
T = (BitTree)malloc(sizeof(BitNode));
T->data = key;
T->lChild = NULL;
T->rChild = NULL;
return 1;
}
if (!SearchBST(T, key))
{
BitTree t = T;
BitTree p = (BitTree)malloc(sizeof(BitNode));
p->data = key;
p->lChild = NULL;
p->rChild = NULL;
while(t != NULL)
{
if (t->data < key)
{
if (t->rChild == NULL)
{
t->rChild = p;
return 1;
}
t = t->rChild;
}
else
{
if (t->lChild == NULL)
{
t->lChild = p;
return 1;
}
t = t->lChild;
}
}
}
}对于插入操作，首先要判断插入的数据是不是根节点。如果不是，则判断是否已经存在，如果不存在，则按照二叉排序树的规则，来进行相应位置的插入。
3 删除
void DeleteBST(BitTree &t, int key)
{
BitTree p = t, f = NULL;
while(p)
{
if (p->data == key)
{
break;
}
f = p; //如果删除的是根节点，则f不为NULL，否则为NULL
if (p->data < key)
{
p = p->rChild;
}
else
{
p = p->lChild;
}
}
if (!p) return ; //如果p为空，即删除的节点不存在，返回退出
BitTree q;
if ((p->lChild) && (p->rChild)) //要删除的节点具有左右孩子
{
q = p; // 当前节点位置赋值给q
BitTree s = p->lChild;
while (s->rChild) //找到要删除节点的先驱节点
{
q = s;
s = s->rChild;
} //如果
p -> data = s->data; //将前驱节点的值赋给要删除的节点，即删除操作
if (q != p) //如果要删除节点的左孩子，没有右孩子，也就是左孩子赋给了删除的节点，则执行else，维护替代节点的左孩子
//否则，将替代节点的左孩子，赋给其父节点的右孩子，这步操作也就是对替代节点所连接的孩子的处理。
{
q->rChild = s->lChild;
}
else
{
q->lChild = s->lChild;
}
free(s);//替代的节点已经赋值给删除的节点，替代的节点也就多余，所以删除。
return ;//这是最难处理的一种情形，左右孩子都有。
}
else if (!p->rChild)//没有右孩子，这里也包括既没有左孩子，又没有右孩子的情况，下同
{
q = p;
p = p->lChild;
}
else if(!p->lChild)//没有左孩子
{
q = p;
p = p->rChild;
}
if (!f) t = p; //如果删除的是根节点，则将新的替换过的根节点，赋值给t
else if(q == f->lChild) f->lChild = p;//f指向的是删除节点的父节点，也就是将处理过的替代节点接回去
else f->rChild = p;
free(q);//q属于删除的节点，所以释放掉
}删除是比较复杂的，分为4种情形，删除的节点只有左孩子，只有右孩子，都有，都没有，还有一种特殊的，删除的是根节点，则需要对传入的t进行处理，由于代码给的注释已经很详细了，这里就不讲了。😶
4 全部代码
#include<bits/stdc++.h>
using namespace std;
typedef int dataType;
typedef struct BitNode
{
dataType data;
struct BitNode *lChild, *rChild;
}BitNode, *BitTree;
int SearchBST(BitTree t, int key)
{
if (t == NULL)
{
return 0;
}
else
{
if (t->data == key)
{
return 1;
}
else if (t->data > key)
{
return SearchBST(t->lChild, key);
}
else
{
return SearchBST(t->rChild, key);
}
}
}
int InsertBST(BitTree &T, int key)
{
if (T == NULL)
{
T = (BitTree)malloc(sizeof(BitNode));
T->data = key;
T->lChild = NULL;
T->rChild = NULL;
return 1;
}
if (!SearchBST(T, key))
{
BitTree t = T;
BitTree p = (BitTree)malloc(sizeof(BitNode));
p->data = key;
p->lChild = NULL;
p->rChild = NULL;
while(t != NULL)
{
if (t->data < key)
{
if (t->rChild == NULL)
{
t->rChild = p;
return 1;
}
t = t->rChild;
}
else
{
if (t->lChild == NULL)
{
t->lChild = p;
return 1;
}
t = t->lChild;
}
}
}
}
void show(BitTree t)
{
if (t == NULL)
{
return ;
}
printf("%d\t",t->data);
show(t->lChild);
show(t->rChild);
}
void DeleteBST(BitTree &t, int key)
{
BitTree p = t, f = NULL;
while(p)
{
if (p->data == key)
{
break;
}
f = p; //如果删除的是根节点，则f不为NULL，否则为NULL
if (p->data < key)
{
p = p->rChild;
}
else
{
p = p->lChild;
}
}
if (!p) return ; //如果p为空，即删除的节点不存在，返回退出
BitTree q;
if ((p->lChild) && (p->rChild)) //要删除的节点具有左右孩子
{
q = p; // 当前节点位置赋值给q
BitTree s = p->lChild;
while (s->rChild) //找到要删除节点的先驱节点
{
q = s;
s = s->rChild;
} //如果
p -> data = s->data; //将前驱节点的值赋给要删除的节点，即删除操作
if (q != p) //如果要删除节点的左孩子，没有右孩子，也就是左孩子赋给了删除的节点，则执行else，维护替代节点的左孩子
//否则，将替代节点的左孩子，赋给其父节点的右孩子，这步操作也就是对替代节点所连接的孩子的处理。
{
q->rChild = s->lChild;
}
else
{
q->lChild = s->lChild;
}
free(s);//替代的节点已经赋值给删除的节点，替代的节点也就多余，所以删除。
return ;//这是最难处理的一种情形，左右孩子都有。
}
else if (!p->rChild)//没有右孩子，这里也包括既没有左孩子，又没有右孩子的情况，下同
{
q = p;
p = p->lChild;
}
else if(!p->lChild)//没有左孩子
{
q = p;
p = p->rChild;
}
if (!f) t = p; //如果删除的是根节点，则将新的替换过的根节点，赋值给t
else if(q == f->lChild) f->lChild = p;//f指向的是删除节点的父节点，也就是将处理过的替代节点接回去
else f->rChild = p;
free(q);//q属于删除的节点，所以释放掉
}
int main()
{
BitTree t = NULL;
int data[16] = {62,58,47,35,51,29,37,36,49,56,48,50,88,73,99,93};
for (int i = 0; i < 16; ++i)
{
InsertBST(t, data[i]);
}
DeleteBST(t, 36);
show(t);
//printf("%d",SearchBST(t,62));
return 0;
}到这里这篇文章就结束了。如果有错误，可以在下方评论，或者私聊我😉，我会及时改正的。
如果看了有收获，可以点赞加关注😉，看计算机小白的成长之路。
