【数据结构】18 二叉搜索树(查找,插入,删除)

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

定义

二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。
一个二叉搜索树可以为空,如果它不为空,它将满足以下性质:

  1. 非空左子树的所有键值小于其根节点的键值
  2. 非空右子树的所有键值都大于其根结点的键值
  3. 左、右子树都是二叉树

动态查找

查找操作Find

在二叉搜索树中查找关键字为X的结点,返回其所在结点的地址。查找过程如下:

  1. 查找从树的根节点开始,若树为空,返回NULL
  2. 搜索树非空,则根节点关键字和X比较,依据结果,需要进行不同的处理
    若根节点键值小于X,在根节点右子树中查找
    若根节点的键值大于X,在根节点的左子树中查找
    若两者比较结果相等,搜索完成。

递归代码

Position Find_RE(BinTree BT, ElementType X) {
	if (!BT) {
		return NULL;
	}
	if (X > BT->Data) {
		return Find_RE(BT->Right, X);
	}
	else if(X < BT->Data)
	{
		return Find_RE(BT->Left, X);
	}
	else
	{
		return BT;
	}
}

迭代函数

Position Find_D(BinTree BT, ElementType X) {
	BinTree T = BT;
	while (T) {
		if (T->Data > X) {
			T = T->Left;
		}
		else if (T->Data < X) {
			T = T->Right;
		}
		else
		{
			return T;
		}
	}
}

查找最大和最小元素

根据二叉搜索树的性质,最大元素一定在最右分支的尾端,最小元素一定在最左分支的尾端。
递归函数

Position FindMin(BinTree BT) {
	if (!BT) {
		return NULL;
	}
	else if(!BT->Left)
	{
		return BT;
	}
	else
	{
		return FindMin(BT->Left);
	}
}

迭代函数

Position FindMinD(BinTree BT) {
	BinTree T = BT;
	while (T->Left) {
		T = T->Left;
	}
	return T;
}

找最大值只需要把left换成right

插入

BinTree Insert(BinTree BT, ElementType X) {
	if (!BT) {
		BT = (BinTree)malloc(sizeof(struct TNode));
		BT->Data = X;
		BT->Left = BT->Right = NULL;
	}
	else {
		if (X > BT->Data) {
			BT->Right =  Insert(BT->Right, X);
		}
		else if (X < BT->Data) {
			BT->Left =  Insert(BT->Left, X);
		}
		
	}
	return BT;
}

删除

二叉搜索树的删除比较复杂,需要考虑节点的位置

  1. 叶结点
    可以直接删除,将其父节点指针置空即可。
  2. 只有一个孩子结点
    要修改其父节点的指针,指向要删除结点的孩子结点。
  3. 有左、右两颗树
    究竟用哪颗子树的根结点来填充删除节点的位置?有两种选择方式:选择左子树的最大元素,或者选择右子树的最小元素。无论哪种方式,最后被选择的结点必定最多只有一个孩子。
    【数据结构】18 二叉搜索树(查找,插入,删除),数据结构,C\C++,数据结构

采用右子树的最小元素的删除代替策略。
代码思路: 先找到要删除元素的位置,若其具有左右子树,找到该位置的右子树里面的最小元素,赋值到该位置上,在其右子树中删除最小元素(递归调用),若只有一个子树或者没有,易操作。文章来源地址https://www.toymoban.com/news/detail-834985.html


BinTree DeleteBT(BinTree BT, ElementType X) {
	Position p;
	if (!BT) {
		printf("can't find the node\n");
	}
	else {
		if (X > BT->Data) {
			BT->Right = DeleteBT(BT->Right, X);
		}
		else if (X < BT->Data) {
			BT->Left = DeleteBT(BT->Left, X);
		}
		else {
			if (BT->Left && BT->Right) {
				//FIND THE Min OF Right TREE
				p = FindMin(BT->Right);
				BT->Data = p->Data;
				BT->Right = DeleteBT(BT->Right, p->Data);
			}
			else {
				p = BT;
				if (!BT->Left) {
					BT = BT->Right;
				}
				else { BT = BT->Left; }
				free(p);
			}
		}
	}
	return BT;
}

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

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

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

相关文章

  • 【数据结构】单链表基本操作:查找、插入、删除、创建

     链表由结点组成,结点由数据域和指针域组成。其中,数据域存放的就是数据元素,指针域存放下一个结点的地址。数据元素可以只有一个,也可以有多个不同类型的数据元素,甚至是数组。下图和代码来自《C Primer Plus》,该链表每个节结点同时含char类型和int类型。 ​​

    2024年02月02日
    浏览(57)
  • 【数据结构(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. 二叉搜索树(BST)   1.1 二叉搜索树概念   1.2 二叉搜索树操作         1.2.1 二叉搜索树的查找         1.2.2 二叉搜索树的插入          1.2.3 二叉搜索树的删除 2. 二叉搜索树的实现   2.1BST基本结构   2.2 BST操作成员函数(非递归)   2.3 BST操作成员函数(递归) 3. 二

    2024年02月06日
    浏览(59)
  • 【数据结构】线性表(一)线性表的定义及其基本操作(顺序表插入、删除、查找、修改)

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(64)
  • 【数据结构】(顺序表)C语言实现线性表顺序存储的创建、插入、删除、查找、输出等基本操作(附完整代码)

    要求:利用书本上的线性表的顺序存储结构定义 #define MAXSIZE 100 //顺序表可能达到的最大长度 typedef struct{ ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) } SqList; 1)编写完成下列功能的函数: (1)初始化一个线性表

    2024年04月28日
    浏览(46)
  • 【数据结构】链表:插入、删除

    我是通过b站的教程(如下图)学习的,这里记录下学习笔记。 数据结构简单导言(为什么会出现数据结构?)。在日常生活中,为了组织不同类型的数据,我们需要不同类型的结构,帮助我们更高效更方便的找到想要的数据。 目录 链表引言 使用数组实现动态列表的弊端 1.插入和

    2024年02月02日
    浏览(48)
  • 二叉排序树的查找、插入、删除

    目录 二叉排序树的定义 二叉排序树的查找 二叉排序树的插入 二叉排序树的定义 二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树: 1) 若左子树非空,则左子树上所有结点均小于根结点的关键

    2024年02月07日
    浏览(36)
  • 数据结构-二叉排序树(建立、查找、修改)

    二叉排序树是动态查找表的一种,也是常用的表示方法。 其中,它具有如下性质: 1.若它的左子树非空,则其左子树的所有节点的关键值都小于根节点的关键值。 2.若它的右子树非空,则其右子树的所有节点的关键值都大于根结点的关键值。 3.它的左右子树也分别都是二叉排

    2024年02月04日
    浏览(40)
  • 数据结构--单链表的插入&删除

    目标 单链表的插入(位插、前插、后插) 单链表的删除 按为序插入(带头结点) ListInsert(L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。 思路:找到第i-1个结点,将新结点插入其后 代码实现 时间复杂度 最好时间复杂度 O(1) 最坏时间复杂度 O(1) 平均时间复杂度 O(1) 按位

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

    目录 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

领红包