C语言实现二叉排序树（二叉搜索树、二叉查找树）的插入与删除操作_编写程序完成二叉排序树的建立、查找、插入、删除及输出操作

准备工作

首先定义结构体，并初始化一棵二叉排序树，本质是二叉树的链式存储结构，不作为本篇重点，将代码展示如下

typedef struct BinaryTree{
	int data;
	struct BinaryTree* left;
	struct BinaryTree* right;
}BSTNode, *BSTree;//定义结构体变量与结构体指针变量
BSTree init(int data)
{
	BSTree ro = (BSTree)malloc(sizeof(BSTNode));
	if (ro==NULL)
	{
		printf("error");
		return NULL;
	}
	ro->data = data;
	ro->left = ro->right = NULL;
	return ro;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对于二叉排序树的插入操作，可以通过递归实现与非递归实现，下面分别讨论

非递归插入

插入操作是基于查找操作实现的，即要想将一个节点插入BST中，就要查找该节点理应放置的位置。而这个查找操作正类似于二分查找，同时这也体现了BST的一个特性，即便于查找。

首先创建一个节点，数据域存放要插入的数据值，指针域置空。
假定该节点已经插入树中，我们要先进行查找操作。让一个指针p指向根节点，然后判断要插入的值与p指向的节点的值的大小关系，并根据判断结果来让p指针指向其左孩子或者右孩子，如此循环，直到判断结果为值相等。最终结果是找到了理应插入的位置。
但是该节点并不存在于树中，故进行完查找操作后，p指针最终指向的是NULL，代码如下

while (p!=NULL)
{
	//x为要插入的数据
	if (x > p->data){
		p = p->right;
	}
	else{
		p = p->left;
	}
}
1
2
3
4
5
6
7
8
9
10

什么？最终p指向的是NULL，这是一个不确定的位置，我们也就无法找到其父亲。
那么，如何找到其父亲呢？不难想到，我们只需定义一个指针pre始终指向p指针的父亲就好了。代码如下

BSTNode* pre = NULL;//根节点的父亲为空
BSTNode* p = ro;
while (p)
{
	if (x > p->data)
	{
		pre = p;
		p = p->right;
	}
	else
	{
		pre = p;
		p = p->left;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如此一来，我们就找到了要插入的位置，最终只需进行一次判断，将其插入就好

void insert_1(BSTree ro, int x)
{
	//初始化节点
	BSTree s = init(x);
	//插入节点
	BSTNode* pre = NULL;
	BSTNode* p = ro;
	while (p)
	{
		if (x > p->data)
		{
			pre = p;
			p = p->right;
		}
		else
		{
			pre = p;
			p = p->left;
		}
	}
	if (x < pre->data)
	{
		pre->left = s;
	}
	else {
		pre->right = s;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

递归插入

首先，要理清思路。我们要实现一个函数insert，返回值是指向一棵树的指针（因为你将节点插入树中，必然改变了这棵树，所以要将这棵树返回来），参数是指向要插入树的指针ro与要插入的数据k。需要格外注意的是，该函数的功能是在以ro为根节点的树中插入数据k。

//函数声明
BSTree insert(BSTree ro,int k);
1
2

既然是递归函数，那就要有递归出口，同时在运行时要经历两步，一是“递”，二是“归”。
以该函数为例，“递”表现在不断查找所要插入的位置，直到满足递归出口的条件，之后开始“归”，即层层向上返，这里是返回指向一棵树的指针，可以理解为将树或者节点返回给上一层的递归调用。
不难想到，递归出口就是ro==NULL,这也意味着查找的结束。另外,我们要将ro->data与k值大小进行判断，这便是查找的过程。完整代码如下

BSTree insert(BSTree ro,int k)
{
	if (ro == NULL)
	{
		BSTree s = init(k);
		return s;
	}
	else if (k < ro -> data)
	{
		ro->left=insert(ro->left, k);//去ro的左子树中插入k
		return ro;
	}
	else {
		ro->right = insert(ro->right, k);//去ro的右子树中插入k
		return ro;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们要时刻关注insert函数的功能，是在以ro为根节点的树中插入数据k。当k < ro -> data时，就在以ro的左子树为根的树中插入k，插入完成后将函数返回值赋值给ro->left，这样就能在最后两层递归调用时，将k所在节点s插入到合适位置。k > ro -> data时同理。
可以这样理解，当我层层往下递，不断向下查找完成之后，就来到了递归出口，即ro==NULL，注意这里的ro指向的位置正是我们应该把k插入的位置。我们记录这个特殊的ro为c。在最终执行函数insert(c, k)时，由于满足递归出口的条件，我们创建了一个节点s，用来存储数据k，之后我们return s，“归”便开始了，即层层向上返回。
为了方便理解，我们把将要插入的节点s的理应父亲节点记作f,那么，在递归出口这里返回上去就来到了函数insert(f,k)；并继续执行里面的语句ro->left=insert(ro->left, k); （假如k < f -> data）这里实际上是f->left=insert(c, k);由于递归出口处我们返回了节点s，于是等价于f->left=s。如此以来我们便将节点s插入到了合适的位置，这就是用ro->left或者ro->right
接收返回值的原因。由于这里的f发生了改变，所以我们还要将其返回。

删除操作

理解了递归插入，再看删除，也是如法炮制。首先删除也是基于查找，与插入操作不谋而合，代码如下

BSTree del(BSTree ro, int k)
{
	if (k < ro->data)
	{
		ro->left=del(ro->left, k);
		return ro;
	}
	else if (k > ro->data)
	{
		ro->right = del(ro->right, k);
		return ro;
	}
	//部分代码
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

由于要删除的节点存在于树中，那么递归出口便是k==ro->data。倘若满足递归出口条件，那么就要进行删除ro节点操作，由于ro的孩子数未知，所以我们要分类讨论。

1. 假如ro没有孩子，直接删除ro
2. 假如ro只有左孩子，删除ro，让其左孩子代替该位置
3. 假如ro只有右孩子，删除ro，让其右孩子代替该位置
4. 假如ro左右孩子都存在，那就让中序遍历下的其前一个(后一个也可)节点代替该位置

我们尝试写下前三种情况

	if(!ro->left&&!ro->right)	//ro左右孩子都为NULL
	{
		free(ro);
		ro == NULL;
		return NULL;
	}
	else if(ro->left&&!ro->right)	//ro只有左孩子存在
	{
		BSTNode* q = ro->left;
		free(ro);
		ro == NULL;
		return q;
	}
	else if(ro->right&&!ro->left)	//ro只有右孩子存在
	{
		BSTNode* q = ro->right;
		free(ro);
		ro == NULL;
		return q;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除ro节点只需释放ro指向的空间，然后将ro置空，以防变为野指针。至于让孩子代替父亲的位置，我们只需直接返回这个孩子即可，这样在“归”时就可以直接将其插入到合适的位置，从而完成代替。
注意这里可以进一步简化代码，我们可以将第一种情况看作第二种或者第三种（这里以第三种为例）的一个特殊情况，即ro有一个孩子，只不过为NULL。简化的代码如下

if(ro->left&&!ro->right)	//ro只有左孩子存在
{
	BSTNode* q = ro->left;
	free(ro);
	ro == NULL;
	return q;
}
else if(ro->right&&!ro->left||!ro->left&&!ro->right)	//ro只有右孩子存在或者左右孩子都为NULL
{
	BSTNode* q = ro->right;
	free(ro);
	ro == NULL;
	return q;
}
//注：这些条件都会在后续完整代码得到简化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对于第四种情况，我们以用中序遍历紧挨着的前一个节点(记作t)代替为例。根据中序遍历，显然t就是ro的左子树中最靠右的节点。那么如何代替呢？我们只需将t节点的data赋给ro的data，然后再将t删除即可，代码如下

if (ro->left && ro->right)	//ro左右孩子都存在
{
	BSTNode* p = ro->left;
	//查找ro的左子树中最靠右的节点
	while (p->right)
		p = p->right;
	//代替
	ro->data = p->data;
	//在ro的左子树中删除最靠右的节点
	ro->left=del(ro->left, p->data);
	return ro;
}
1
2
3
4
5
6
7
8
9
10
11
12

这样，删除操作就完成了。完整代码如下

BSTree del(BSTree ro, int k)
{
	if (k < ro->data)
	{
		ro->left=del(ro->left, k);
		return ro;
	}
	else if (k > ro->data)
	{
		ro->right = del(ro->right, k);
		return ro;
	}
	//以下均为k==ro->data满足时
	else if (ro->left && ro->right)	//ro左右孩子都存在
	{
		BSTNode* p = ro->left;
		//查找ro的左子树中最靠右的节点
		while (p->right)
			p = p->right;
		//代替
		ro->data = p->data;
		//在ro的左子树中删除最靠右的节点
		ro->left=del(ro->left, p->data);
		return ro;
	}
	else if(ro->left)	//ro只有左孩子存在
	{
		BSTNode* q = ro->left;
		free(ro);
		ro == NULL;
		return q;
	}
	else	//ro只有右孩子存在或者左右孩子都为NULL
	{
		BSTNode* q = ro->right;
		free(ro);
		ro == NULL;
		return q;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

测试与运行结果

我们可以通过中序遍历来检验是否插入成功与删除成功

void inOrder(BSTree ro)
{
	if (ro == NULL)	return;
	if (ro->left)	inOrder(ro->left);
	printf("%d ", ro->data);
	if (ro->right)	inOrder(ro->right);
}
1
2
3
4
5
6
7

主函数这里，让用户输入节点总数与各个节点的值，从而完成后续操作

int main()
{
	int n;
	scanf("%d", &n);
	int root;
	scanf("%d", &root);
	BSTree ro = init(root);
	int x;
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d", &x);
		insert_1(ro, x);
	}
	printf("插入完成，遍历结果为：");
	inOrder(ro);
	putchar('\n');

	ro=BST_del(ro, 3);
	printf("删除3后，遍历结果为：");
	inOrder(ro);
	putchar('\n');

	ro=BST_del(ro, 10);
	printf("删除10后，遍历结果为：");
	inOrder(ro);
	putchar('\n');
	/*输入样例
	9
	8 3 15 2 6 10 7 12 13
	*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31