数据结构-二叉排序树(建立、查找、修改)

这篇具有很好参考价值的文章主要介绍了数据结构-二叉排序树(建立、查找、修改)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉排序树概念

二叉排序树是动态查找表的一种,也是常用的表示方法。

其中,它具有如下性质:

1.若它的左子树非空,则其左子树的所有节点的关键值都小于根节点的关键值。

2.若它的右子树非空,则其右子树的所有节点的关键值都大于根结点的关键值。

3.它的左右子树也分别都是二叉排序树。

PS:对二叉排序树进行中序遍历,得到的序列,总会是一个升序的数列。

二叉排序树的建立

我们使用C语言来建立。

其中我们对二叉排序树的结构体定义如下:

typedef int ElemType;
typedef struct BTNode{
    ElemType key;
    struct BTNode *lchild,*rchild;
}BTNode,*BSTree;

建立二叉排序树的代码如下:

BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
{
	if(bst==NULL)
		bst = s;
	else{
		if(s->key < bst->key)
			bst->lchild = InsertBST(bst->lchild,s);
		if(s->key > bst->key){
			bst->rchild = InsertBST(bst->rchild,s);
		}
	}
	return bst;
}

BSTree CreateBST()		//建立二叉排序树 
{
	BSTree bst,s;
	int key;
	bst = NULL;
	printf("请输入关键字值,输入-1结束.\n");
	while(1){
		scanf("%d",&key);
		if(key!=-1){
			s = (BSTree)malloc(sizeof(BTNode));
			s->key = key;
			s->lchild = NULL;
			s->rchild = NULL;
			bst = InsertBST(bst,s);
			printf("成功.\n");
		}
		else
			break;
	}
	return bst;
}

二叉排序树的插入

BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
{
	if(bst==NULL)
		bst = s;
	else{
		if(s->key < bst->key)
			bst->lchild = InsertBST(bst->lchild,s);
		if(s->key > bst->key){
			bst->rchild = InsertBST(bst->rchild,s);
		}
	}
	return bst;
}

BSTree SearchBST(BSTree bst,int key)		//查找关键值key的节点,并且返回这个节点 
{
	if(bst == NULL)
		return NULL;
	else if(key == bst->key)
		return bst;
	else if(key > bst->key)
		return SearchBST(bst->rchild,key);
	else
		return SearchBST(bst->lchild,key);
}

BSTree InsertBST_key(BSTree bst,int key)		//搜寻一个关键值,如果没有就插入 
{
	BSTree s;
	s = SearchBST(bst,key);
	if(s)
		printf("该节点已经存在.");
	else{
		s = (BSTree)malloc(sizeof(BTNode));
		s->key = key;
		s->lchild = NULL;
		s->rchild = NULL;
		s = InsertBST(bst,s);
	}
	return s;
}

查找二叉排序树指定节点的双亲

BSTree SearchBST_F(BSTree bst,int key,BSTree *F)		//F存储key关键值节点的双亲节点,函数返回key关键值节点. 
{
	if(bst == NULL)
		return NULL;
	if(key == bst->key)
		return bst;
	else{
		*F = bst;
		if(key < bst->key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}

 删除二叉排序树中某个节点:

对于删除二叉排序树的节点,我们有必要花大功夫来讨论一下。

对于删除二叉排序树的某个节点,大致有以下四种情况:

假设我们要删除的节点指定为P

1.P节点的左右子树都为空

此时删除P节点,只需要P节点的父节点的左/右子树赋值NULL,并且free掉P节点即可。

数据结构二叉排序树创建,数据结构,数据结构

值得注意的是,还有一种特殊情况,那就是P节点本身就是根节点,也就是这个树只有P节点一个

节点。

那么此时,我们只需要返回NULL,并且free掉P节点即可。

数据结构二叉排序树创建,数据结构,数据结构

2.P节点的左子树为空

在这种情况下,我们注意到P的右子树不是空的,如下图所示:

数据结构二叉排序树创建,数据结构,数据结构

此时我们只需要令P节点的父节点C的右子树/左子树为P的右子树即可。

不过值得注意的是,此时仍有可能P是根节点,此时我们需要令根节点 = p的右子树,并且free掉p

节点即可。

数据结构二叉排序树创建,数据结构,数据结构

3.P节点的右子树为空

此时我们注意到,这种情况根情况2(P节点的左子树为空)非常相似。

数据结构二叉排序树创建,数据结构,数据结构

此时我们只需要令P的父节点C的左/右子树等于P的左子树即可。

不过此时P节点仍有可能作为根节点出现,此时我们只需要令根节点等于P的左子树即可。

数据结构二叉排序树创建,数据结构,数据结构

4.P节点的左右子树都不为空

这种情况无疑是最复杂的一种情况,因为此时我们要牵扯一个大小的排序。

因此,我们可以令P节点的Key值等于P节点的直接前驱(直接后驱)的Key值,之后删掉直接前驱(直

接后驱)即可。

数据结构二叉排序树创建,数据结构,数据结构

注意到此时的P节点的直接前驱是G(即P节点的左子树的最右侧的一个节点)。

那么此时我们可以令P节点的Key值等于G节点的Key值,同时free掉G节点即可完成操作。

不过,比较重要的一点是,G节点的左子树不一定为空此时我们仍需要让G节点的节点的右子

等于G节点的左子树

注意到,当P节点作为根结点的时候并不会出现特殊的情况,但是当P节点的前驱节点就是P的左子

,我们需要另外的讨论,如下图所示:

数据结构二叉排序树创建,数据结构,数据结构

注意到此时P的直接前驱节点就是D,但是如果我们直接删除D,那么D的左子树此时应该给P的

子树。

注意到P也是D的一个父节点,P同时还是D的一个直接后继节点,此时就是一种特殊情况,需要让

P左子树等于D左子树,而不是D父节点右子树等于D左子树!!!

代码实现:文章来源地址https://www.toymoban.com/news/detail-767407.html

BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
{
	if(bst == NULL)
		return NULL;
	if(bst->key == key)
		return bst;
	else{
		*F = bst;
		if(bst->key > key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}

BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
{
	BSTree par,s;
	int kind;
	if(!p->lchild && !p->rchild)	//左右子树全为空 
		kind = 1;
	else if(!p->lchild)			//左子树为空 
		kind = 2;
	else if(!p->rchild)			//右子树为空 
		kind = 3;
	else			//左右子树都不为空 
		kind = 4;
	switch(kind){
		case 1:
			if(!f)			//没有父节点,p是根节点, 
				return NULL;
			else{
				if(f->lchild == p)
					f->lchild = NULL;
				else
					f->rchild = NULL;
				free(p);
			}
			break;
		case 2:
			if(!f)			//p是根节点
				bst = bst->rchild;
			else{
				if(p == f->lchild)
					f->lchild = p->rchild;
				else
					f->rchild = p->rchild;
				free(p);
			}
			break;
		case 3:
			if(!f)			//p是根节点 
				bst = bst->lchild;
			else{
				if(p == f->lchild)
					f->lchild = bst->lchild;
				else
					f->rchild = bst->lchild;
			}
			free(p);
			break;
		case 4:
			par = p;		//p节点前驱指针par 
			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
				par = s;
				s = s->rchild;
			}
			p->key = s->key;		//令p节点的值为s节点的值 
			if(par == p)		//特殊情况,s节点刚好是p的左子树 
				par->lchild = s->lchild;
			else
				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
			free(s);		//释放p节点的直接前驱s 
			break;
	}	
	return bst;
}

BSTree SearchDeleteBST(BSTree bst,int key)
{
	BSTree f = NULL,p;
	p = SearchBST_F(bst,key,&f);
	if(p){
		bst = DeleteBST(bst,p,f);
	}
	else
		printf("该节点不存在.\n");
	return bst;
} 

二叉排序树的所有代码汇总: 

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
typedef struct BSNode{
	ElemType key;
	struct BSNode *lchild,*rchild;
}BSNode,*BSTree;

BSTree SearchBST(BSTree bst,BSTree s)
{
	if(bst == NULL)
		bst = s;
	else{
		if(bst->key > s->key)
			bst->lchild = SearchBST(bst->lchild,s);
		if(bst->key < s->key)
			bst->rchild = SearchBST(bst->rchild,s);
	}
	return bst;
}

BSTree CreateBSTree()
{
	int key;
	BSTree bst = NULL;
	printf("请输入节点关键值,输入-1结束.\n");
	while(1){
		scanf("%d",&key);
		if(key != -1){
			BSTree s = (BSTree)malloc(sizeof(BSNode));
			s->key = key;
			s->lchild = NULL;
			s->rchild = NULL;
			bst = SearchBST(bst,s);
			printf("创建节点成功.\n");
		}
		else
			break;
		
	}
	return bst;
}

void PostTraverse(BSTree bst)
{
	if(bst){
		PostTraverse(bst->lchild);
		printf("%d ",bst->key);
		PostTraverse(bst->rchild);
	}
}

BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
{
	if(bst == NULL)
		return NULL;
	if(bst->key == key)
		return bst;
	else{
		*F = bst;
		if(bst->key > key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}

BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
{
	BSTree par,s;
	int kind;
	if(!p->lchild && !p->rchild)	//左右子树全为空 
		kind = 1;
	else if(!p->lchild)			//左子树为空 
		kind = 2;
	else if(!p->rchild)			//右子树为空 
		kind = 3;
	else			//左右子树都不为空 
		kind = 4;
	switch(kind){
		case 1:
			if(!f)			//没有父节点,p是根节点, 
				return NULL;
			else{
				if(f->lchild == p)
					f->lchild = NULL;
				else
					f->rchild = NULL;
				free(p);
			}
			break;
		case 2:
			if(!f)			//p是根节点
				bst = bst->rchild;
			else{
				if(p == f->lchild)
					f->lchild = p->rchild;
				else
					f->rchild = p->rchild;
				free(p);
			}
			break;
		case 3:
			if(!f)			//p是根节点 
				bst = bst->lchild;
			else{
				if(p == f->lchild)
					f->lchild = bst->lchild;
				else
					f->rchild = bst->lchild;
			}
			free(p);
			break;
		case 4:
			par = p;		//p节点前驱指针par 
			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
				par = s;
				s = s->rchild;
			}
			p->key = s->key;		//令p节点的值为s节点的值 
			if(par == p)		//特殊情况,s节点刚好是p的左子树 
				par->lchild = s->lchild;
			else
				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
			free(s);		//释放p节点的直接前驱s 
			break;
	}	
	return bst;
}

BSTree SearchDeleteBST(BSTree bst,int key)
{
	BSTree f = NULL,p;
	p = SearchBST_F(bst,key,&f);
	if(p){
		bst = DeleteBST(bst,p,f);
	}
	else
		printf("该节点不存在.\n");
	return bst;
} 

int main()
{
	BSTree bst;
	bst = CreateBSTree();
	SearchDeleteBST(bst,5);
	PostTraverse(bst);
	return 0;
}

到了这里,关于数据结构-二叉排序树(建立、查找、修改)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构07:查找[C++][朴素二叉排序树BST]

    图源:文心一言 考研笔记整理 8k+ 字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_1 二叉排序树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月10日
    浏览(40)
  • 合肥工业大学 宣城校区 数据结构与算法实验 队列、二叉树、查找和排序

    1.实验目标 熟练掌握队列的顺序存储结构和链式存储结构。 熟练掌握队列的有关算法设计,并在循环顺序队列和链队列上实现。 根据具体给定的需求,合理设计并实现相关结构和算法。 2.实验内容和要求 循环顺序队列的实验要求 循环顺序队列结构和运算定义,算法的实现以

    2024年02月11日
    浏览(49)
  • 二叉排序树的插入删除和查找(数据结构实训)(难度系数100)

    二叉排序树的插入删除和查找 pre: 前序遍历 in: 中序遍历 post:后序遍历 insert: 插入,本题中不会出现相同的元素 delete: 删除,删除成功输出TRUE,没有该元素则输出FALSE,删除的方法是如果有左子树,以左子树中最大值作为新的树根,否则,以右子树最小值作为树根。 search:

    2024年01月25日
    浏览(50)
  • 数据结构--建立与输出二叉树

    文章目录 一、问题的描述 二、系统功能设计 三、各个代码部分 四、整体代码及其运行 五、总结 建立与输出二叉树--C语言实现 二叉树是一种特殊的树结构,也是最常见的树结构,二叉树的存储和处理比一般的树简单,而一般的树都能通过转换得到与子对应的二叉树。因此我

    2024年02月10日
    浏览(82)
  • 【数据结构】18 二叉搜索树(查找,插入,删除)

    二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。 一个二叉搜索树可以为空,如果它不为空,它将满足以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值都大于其根结点的键值 左、右子树都是二叉树 在

    2024年02月22日
    浏览(49)
  • 【数据结构(C++)】树型查找——二叉搜索树

    目录 1. 二叉搜索树 1.1 二叉搜索树的概念 1.2 二叉搜索树类模板 1.3 二叉搜索树的操作 1.3.1 查找 1.3.2 插入 1.3.3 删除 1.4 二叉搜索树的性能分析 2. 平衡二叉树 2.1 平衡二叉树的概念 2.2 平衡二叉树类模板 2.3 二叉搜索树的插入 3. 红黑树 3.1 红黑树的概念 3.2 红黑树类模板 二叉搜索

    2024年02月10日
    浏览(42)
  • 【数据结构】二叉查找树和平衡二叉树,以及二者的区别

    目录 1、二叉查找树 1.1、定义  1.2、查找二叉树的优点  1.2、查找二叉树的弊端 2、平衡二叉树 2.1、定义 2.2、 实现树结构平衡的方法(旋转机制) 2.2.1、左旋 2.2.2、右旋 3、总结        二叉查找树又名二叉排序树,亦称二叉搜索树。是每个结点最多有两个子树的树结构

    2024年02月20日
    浏览(49)
  • 数据结构实验报告(四)——查找和排序算法

    1. 掌握顺序查找技术和拆半查找技术以及部分排序算法的设计思想; 2. 掌握查找、部分排序算法的实现与执行过程。 查找算法 1.顺序查找: 从数组第一个元素开始逐个比较,找到后返回相应下标。 2.折半查找: 从数组中间开始比较,如果需查找值比中间值大,则在中间值右

    2024年02月07日
    浏览(45)
  • 数据结构-----二叉排序树

    目录 前言 1.什么是二叉排序树 2.如何构建二叉排序树 3.二叉排序树的操作 3.1定义节点储存方式 3.2插入节点操作 3.2创建二叉排序树 3.4遍历输出(中序遍历) 3.5数据查找操作 3.6获取最大值和最小值 3.7删除节点操作 3.8销毁二叉排序树 4.完整代码         今天我们继续学习新的

    2024年02月03日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包