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

这篇具有很好参考价值的文章主要介绍了二叉搜索树的实现(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

一:准备工作

(1)需要的头文件

(2)树节点结构体描述

(3)初始化

二:指针

三:插入新节点(建树)

(1)生成一个新节点

(2)找插入位置

四:查找和遍历

(1)查找

(2)遍历

五:删除节点

六:全部代码

(1)BinarySearchTree.h(声明)

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

(3)test.c(测试)


前言:

二叉搜索树(Binary Search Tree,BST)是一种非常常见的数据结构,它是一个二叉树,其中每个节点都包含一个键值


对于任何一个结点,它的左子树中的所有键值都小于它的键值,右子树中的所有键值都大于它的键值。基于这样的特性,我们只需要依据根节点的数据域来判断目标节点是在根节点的左子树中还是右子树中,从而提高查找效率。


这种特殊的性质使得对于一个含有N个结点的二叉搜索树,理想情况对它进行查找和插入操作的时间复杂度不超过O(logN),退化成链表的话时间复杂度为O(N),是一种非常高效的数据结构。


注意:本文采用递归来实现,但我不会详细讲递归展开的思路,强烈建议大家先掌握二叉树遍历的递归实现再来看本文(理解不了也可以画一下递归展开图)

二叉树基本接口递归实现:https://blog.csdn.net/2301_76269963/article/details/130231257?spm=1001.2014.3001.5502


一:准备工作

(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需要),为了方便大家理解后续树的结构调整,我单独讲一下。

我们看下面这颗树:

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


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

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

答案当然是不行

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

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

就像这个代码一样:

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


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

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

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

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


三:插入新节点(建树)

(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】按这个思路向下递归,一直到空节点,这个位置就是适合插入的位置

图解:

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

代码:

//搜索二叉树插入,成功返回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。

【2】如果根部节点的值大于x,目标节点只可能在左子树中小于x目标节点只可能在右子树中等于就找到了目标节点,返回节点地址。

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

图解:

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

代码:

//搜索二叉树查找,查找到返回结点地址,否则返回空指针
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)遍历

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

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

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

代码:

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

五:删除节点

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


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


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

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


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

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


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

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

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

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

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

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


代码:

//搜索二叉树删除,删除成功返回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;
}

二叉搜索树的实现(C语言)文章来源地址https://www.toymoban.com/news/detail-461423.html

到了这里,关于二叉搜索树的实现(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(47)
  • 【C++】二叉搜索树的原理及实现

      二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。    文章目录 简介 一、二叉搜索树的概念 二、二叉搜索树的操作及实现 2、1 二叉搜索树的插入 2、1、1 插入的原理 2、1、2

    2024年02月14日
    浏览(53)
  • 二叉搜索树:红黑树的原理和实现

    💭上文我们在遇到问题:二叉搜索树退化到单支导致效率和性能降低时,利用了AVL树解决。但是由于AVL树是一棵绝对平衡的树,每次修改树结构都要保证左右子树高度差的绝对值不超过1,这可能会引发多次旋转。因此,若我们要设计出一棵结构动态变化的二叉搜索树,利用

    2024年02月01日
    浏览(40)
  • 【C++】平衡二叉搜索树的模拟实现

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

    2024年02月09日
    浏览(33)
  • 【C++】AVL(平衡二叉搜索树)树的原理及实现

    文章目录 一、引言 二、AVL树的概念 三、AVL树的插入 3、1 AVL树的简单插入 3、2 旋转分类  3、2、1 新节点插入较高右子树的右侧:左单旋 3、2、2 新节点插入较高左子树的左侧:右单旋 3、2、3 新节点插入较高左子树的右侧:左右双旋(先左后右) 3、2、4 新节点插入较高右

    2024年02月13日
    浏览(49)
  • Java 数据结构篇-实现二叉搜索树的核心方法

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 二叉搜索树的概述         2.0 二叉搜索树的成员变量及其构造方法         3.0 实现二叉树的核心接口         3.1 实现二叉搜索树 - 获取值 get(int key)         3.2 实现二叉搜索树

    2024年02月04日
    浏览(54)
  • Java LeetCode篇-二叉搜索树经典解法(实现:二叉搜索树的最近公共祖先、根据前序遍历建树等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 判断合法         1.1 使用遍历方式实现验证二叉搜索树         1.2 使用递归方式实现验证二叉搜索树         2.0 求范围和         2.1 使用非递归实现二叉搜索树的范围和

    2024年02月03日
    浏览(49)
  • 【数据结构】平衡二叉搜索树(AVL树)——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

      为什么要引入平衡二叉搜索树?   在之前我们学习了二叉搜索树,二叉搜索树的结构类似于一个倒置的树,而左子树的值小于根节点的值,右节点的值大于根节点的值,这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果 在传入的数据为有序或接近有序,

    2024年02月07日
    浏览(49)
  • 二叉树的编程与实现(C语言)

    一 、目的 : 掌握指针变量、动态变量的含义; 掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 掌握指针类型描述、访问和处理二叉树的运算; 二 、环境: operating system version:Win11 CPU instruction set:  x64 Integrated Development Environment:Viusal Studio 2022 三 、内容:

    2024年02月05日
    浏览(38)
  • 二叉树的实现(C语言数据结构)

    目录 一、以下是我们需要实现的功能 二、以下是我们具体功能的实现 1.创建新的结点 2.通过数组生成二叉树  3.先序遍历 4.中序遍历 5.后序遍历   6.层序遍历 7.计算二叉树的结点个数 8.查找指定值为x的结点 9.查找第K层的结点个数 10.统计二叉树叶子结点的个数 11.判断是否为

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包