二叉搜索树的实现(C语言)

前言：

一：准备工作

(1)需要的头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

(2)树节点结构体描述

//重定义数据类型，方便以后更改
typedef int BSTData;

typedef struct BSTNode
{
	//数据域
	BSTData data;
	//指针域，左孩子和右孩子
	struct BSTNode* LeftChild;
	struct BSTNode* RightChild;
}BSTNode;

(3)初始化

    //定义一个结构体指针，初始化为空
	BSTNode* root = NULL;

二：指针

插入新节点和删除节点有可能需要修改节点的指针域，因此需要传入二级指针来进行修改(C需要)，为了方便大家理解后续树的结构调整，我单独讲一下。

我们看下面这颗树：

---

如果我们要让p1的右孩子为C(即修改p1的指针域)，下面这段代码可以吗？

答案当然是不行

原因：形参不过是实参的一份临时拷贝，两者在不同空间，你给了我结构体指针，我可以通过指针找到结构体空间并修改成员，但要更改这个指针本身是做不到的。

就像这个代码一样：

---

我们可以传二级指针来进行修改，虽然依然是一份临时拷贝，但是可以通过这个二级指针找到一级指针空间来进行修改。

三：插入新节点(建树)

(1)生成一个新节点

//生成一个新结点，很简单
BSTNode* BuyNewNode(BSTData x)
{
	BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
	if (NewNode == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	NewNode->LeftChild = NewNode->RightChild = NULL;
	NewNode->data = x;
	return NewNode;
}

(2)找插入位置

插入新节点后要保证二叉树任何一个结点，它的左子树中的所有键值都小于它的键值，右子树中的所有键值都大于它的键值。

---

【1】设待插入数据为x。

【2】如果根部节点的值大于x，我们要把新节点插入到左子树中，小于x插入到右子树中，等于x不可以插入(如果搜索二叉树允许相同数据，那么相同的数据会放在同一个节点上，会导致树的结构变得不平衡，甚至可能会退化成链表。这样会极大地影响搜索二叉树的搜索效率，而且也违反了搜索二叉树的定义)。

【3】按这个思路向下递归，一直到空节点，这个位置就是适合插入的位置。

图解：

代码：

//搜索二叉树插入,成功返回0，失败返回-1
//可能改变指针域，传二级
int BSTInsert(BSTNode** root, BSTData x)
{
	//如果为空，生成一个新结点并链接
	if (*root == NULL)
	{
		BSTNode* NewNode = BuyNewNode(x);
		*root = NewNode;
		return 0;
	}
	//不为空，看是插入右子树中还是左子树中
	//小于插入左子树
	if (x < (*root)->data)
	{
		return BSTInsert(&(*root)->LeftChild, x);
	}
	//大于插入右子树
	else if (x > (*root)->data)
	{
		return BSTInsert(&(*root)->RightChild, x);
	}
	//相等不能插入，返回-1
	else
	{
		return -1;
	}
}

四：查找和遍历

(1)查找

查找的思路和找插入位置基本是一样的。

【1】设待查找数据为x。

【3】按这个思路向下递归，如果到空节点，说明树中没有这个节点，返回空。

图解：

代码：

//搜索二叉树查找,查找到返回结点地址，否则返回空指针
BSTNode* BSTFind(BSTNode* root, BSTData x)
{
	//如果这个结点是目标结点或者 
	//已经走到空(未找到返回空)
	if ((root->data == x) || (root == NULL))
	{
		return root;
	}

	//不是就查找子树，比x大在右树中查找，小在左树中查找
	if (x > root->data)
	{
		return BSTFind(root->RightChild, x);
	}
	else
	{
		return BSTFind(root->LeftChild, x);
	}
}

(2)遍历

遍历就不细讲了，文章开头的链接有，这里只是想单独讲一点。

基于搜索二叉树的性质，我们采用中序遍历的方式(先遍历左子树再访问根部节点最后遍历右子树)来遍历二叉搜索树，会得到一个有序的序列，利用中序遍历可以方便我们观察搜索二叉树的创建是否成功以及还原树的逻辑结构。

代码：

//搜索二叉树遍历(中序)
void InOrder(BSTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	InOrder(root->LeftChild);
	printf("%d ", root->data);
	InOrder(root->RightChild);
}

五：删除节点

找到待删除节点并不困难，难点在于删除后维持搜索二叉树的结构，我们可以把删除节点分成四种情况。

---

①节点不存在，直接返回-1即可

---

②节点为叶子节点(左右子树都为空)，修改父亲节点的指针域为空后释放该节点即可。

---

③节点只有左子树或者右子树，另一边为空，修改父亲节点指针域为该节点不为空的子树根部后释放该节点即可。

---

④节点左右子树均不为空。

【1】为了维持搜索树的结构，我们先从该节点(原节点)左转一步，然后一直右转到尽头，这个时候找到的值为左子树中的最大值。

【2】我们把这个值赋值给原节点，将它的父亲节点指针域置空后删除这个节点。

(这个节点要么是叶子节点要么只有一边不为空，可以利用删除函数去递归删除)

【3】这样不仅维持了搜索树的结构(对于任何一个结点，它的左子树中的所有键值都小于它的键值，右子树中的所有键值都大于它的键值)，也达到了删除的效果。

---

代码：

//搜索二叉树删除,删除成功返回0，失败返回-1
//可能改变指针域，传二级
int BSTDelete(BSTNode** root, BSTData x)
{
	//情况①，节点不存在
	if (*root == NULL)
	{
		return -1;
	}

	//找到了
	if ((*root)->data == x)
	{
		BSTNode* tmp = NULL;
		//情况③只有左子树(左右子树都为空的情况②也可以实现)
		if ((*root)->RightChild == NULL)
		{
			tmp = *root;
			//让父亲结点指针域指向待删除结点的左子树
			*root = (*root)->LeftChild;
			free(tmp);
		}
		//情况③只有右子树
		else if ((*root)->LeftChild == NULL)
		{
			tmp = *root;
			//让父亲结点指针域指向待删除结点的右子树
			*root = (*root)->RightChild;
			free(tmp);
		}
		//情况④左右子树都不为空
		else
		{
			tmp = (*root)->LeftChild;
			while (tmp->RightChild != NULL)
			{
				tmp = tmp->RightChild;
			}
			//把最右结点值赋值给现结点
			(*root)->data = tmp->data;
			//递归删除最右结点,在现节点的左子树中找要删除的节点
			BSTDelete(&((*root)->LeftChild), tmp->data);
		}
		return 0;
	}
	//如果x大于现结点值，目标结点在右子树中
	else if (x > (*root)->data)
	{
		return BSTDelete(&(*root)->RightChild, x);
	}
	//如果x小于现结点值，目标结点在左子树中
	else
	{
		return BSTDelete(&(*root)->LeftChild, x);
	}
}

六：全部代码

(1)BinarySearchTree.h(声明)

#pragma once
#include <stdio.h>
#include <stdlib.h>

//重定义数据类型，方便以后更改
typedef int BSTData;

typedef struct BSTNode
{
	//数据域
	BSTData data;
	//指针域，左孩子和右孩子
	struct BSTNode* LeftChild;
	struct BSTNode* RightChild;
}BSTNode;

//搜索二叉树插入,成功返回0，失败返回-1
int BSTInsert(BSTNode** root, BSTData x);

//搜索二叉树遍历(中序)
void InOrder(BSTNode* root);

//搜索二叉树查找,查找到返回结点地址，否则返回空指针
BSTNode* BSTFind(BSTNode* root, BSTData x);

//搜索二叉树删除,删除成功返回0，失败返回-1
int BSTDelete(BSTNode** root, BSTData x);

(2)BinarySearchTree.c(函数具体实现)

#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"

//生成一个新结点，很简单
BSTNode* BuyNewNode(BSTData x)
{
	BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
	if (NewNode == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	NewNode->LeftChild = NewNode->RightChild = NULL;
	NewNode->data = x;
	return NewNode;
}


//搜索二叉树遍历(中序)
void InOrder(BSTNode* root)
{
	if (root == NULL)
	{
		printf("空 ");
		return;
	}
	InOrder(root->LeftChild);
	printf("%d ", root->data);
	InOrder(root->RightChild);
}


//搜索二叉树插入,成功返回0，失败返回-1
//可能改变指针域，传二级
int BSTInsert(BSTNode** root, BSTData x)
{
	//如果为空，生成一个新结点并链接
	if (*root == NULL)
	{
		BSTNode* NewNode = BuyNewNode(x);
		*root = NewNode;
		return 0;
	}
	//不为空，看是插入右子树中还是左子树中
	//小于插入左子树
	if (x < (*root)->data)
	{
		return BSTInsert(&(*root)->LeftChild, x);
	}
	//大于插入右子树
	else if (x > (*root)->data)
	{
		return BSTInsert(&(*root)->RightChild, x);
	}
	//相等不能插入，返回-1
	else
	{
		return -1;
	}
}


//搜索二叉树查找,查找到返回结点地址，否则返回空指针
BSTNode* BSTFind(BSTNode* root, BSTData x)
{
	//如果这个结点是目标结点或者 
	//已经走到空(未找到返回空)
	if ((root->data == x) || (root == NULL))
	{
		return root;
	}

	//不是就查找子树，比x大在右树中查找，小在左树中查找
	if (x > root->data)
	{
		return BSTFind(root->RightChild, x);
	}
	else
	{
		return BSTFind(root->LeftChild, x);
	}
}


//搜索二叉树删除,删除成功返回0，失败返回-1
//可能改变指针域，传二级
int BSTDelete(BSTNode** root, BSTData x)
{
	//情况①，节点不存在
	if (*root == NULL)
	{
		return -1;
	}

	//找到了
	if ((*root)->data == x)
	{
		BSTNode* tmp = NULL;
		//情况③只有左子树(左右子树都为空的情况②也可以实现)
		if ((*root)->RightChild == NULL)
		{
			tmp = *root;
			//让父亲结点指针域指向待删除结点的左子树
			*root = (*root)->LeftChild;
			free(tmp);
		}
		//情况③只有右子树
		else if ((*root)->LeftChild == NULL)
		{
			tmp = *root;
			//让父亲结点指针域指向待删除结点的右子树
			*root = (*root)->RightChild;
			free(tmp);
		}
		//情况④左右子树都不为空
		else
		{
			tmp = (*root)->LeftChild;
			while (tmp->RightChild != NULL)
			{
				tmp = tmp->RightChild;
			}
			//把最右结点值赋值给现结点
			(*root)->data = tmp->data;
			//递归删除最右结点,在现节点的左子树中找要删除的节点
			BSTDelete(&((*root)->LeftChild), tmp->data);
		}
		return 0;
	}
	//如果x大于现结点值，目标结点在右子树中
	else if (x > (*root)->data)
	{
		return BSTDelete(&(*root)->RightChild, x);
	}
	//如果x小于现结点值，目标结点在左子树中
	else
	{
		return BSTDelete(&(*root)->LeftChild, x);
	}
}

(3)test.c(测试)

#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"

void text1()
{
	//一个节点指针，初始化为空
	BSTNode* root = NULL;
	BSTInsert(&root, 15);
	BSTInsert(&root, 6);
	BSTInsert(&root, 18);
	BSTInsert(&root, 3);
	BSTInsert(&root, 7);
	BSTInsert(&root, 17);
	BSTInsert(&root, 20);
	BSTInsert(&root, 2);
	BSTInsert(&root, 4);
	BSTInsert(&root, 13);

	printf("中序遍历>:");
	InOrder(root);

	if (BSTFind(root, 17))
	{
		printf("\n查找成功\n");
	}
		
	if (BSTInsert(&root, 13))
	{
		printf("插入失败\n");
	}

	printf("中序遍历>:");
	InOrder(root);

	if (BSTDelete(&root, 17))
	{
		printf("\n删除失败\n");
	}
	else
	{
		printf("\n删除成功\n");
	}
		
	printf("中序遍历>:");
	InOrder(root);
}

int main()
{
	text1();
	return 0;
}