本文介绍了二叉排序树最基本的三种操作查找,插入和删除。
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;
}
到这里这篇文章就结束了。如果有错误,可以在下方评论,或者私聊我😉,我会及时改正的。
如果看了有收获,可以点赞加关注😉,看计算机小白的成长之路。