【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23)

这篇具有很好参考价值的文章主要介绍了【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

大家好吖,欢迎来到 YY 滴数据结构系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁
主要内容含:
【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构

欢迎订阅 YY滴C++专栏!更多干货持续更新!以下是传送门!

  • YY的《C++》专栏
  • YY的《C++11》专栏
  • YY的《Linux》专栏
  • YY的《数据结构》专栏
  • YY的《C语言基础》专栏
  • YY的《初学者易错点》专栏
  • YY的《小小知识点》专栏

一.二叉搜索树的基本概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  1. 若它的左子树不为空,则 左子树 上所有节点的值都 小于 根节点的值
  2. 若它的右子树不为空,则 右子树 上所有节点的值都 大于 根节点的值
  3. 它的 左右子树 也分别为二叉搜索树 ;
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构

二.增删查改基本操作

【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构

//结点模板
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
//在二叉搜索树模板中
typedef BSTreeNode<K> Node;

1.二叉搜索树的查找(分析&代码演示)

分析

  • 从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找
  • 最多查找高度次 ,走到到空,还没找到,这个值不存在。

代码演示

//查找操作
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)//从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找 
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;//最多查找高度次 ,走到到空,还没找到,这个值不存在。
	}

2.二叉搜索树的插入(分析&代码演示)

分析

  • 树为空,则直接新增节点,赋值给root指针
  • 树不空, 按二叉搜索树性质的查找方式(前后指针) 找到插入位置,插入新节点

代码演示

//插入操作
	bool Insert(const K& key)
	{
	//树为空,则直接新增节点,赋值给root指针
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		
	//树不空, 按二叉搜索树性质的查找方式(前后指针) 找到插入位置,插入新节点
		Node* parent = nullptr;//后指针
		Node* cur = _root;//前指针
		while (cur)
		{
			if (cur->_key < key)//比keycur的_key大,往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_key > key)//比keycur的_key小,往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
//cur走到空了,开始给插入的key值创建结点,根据其比后一个结点(parent)大还是小,决定其是插在左还是右
		cur = new Node(key); 
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

3.二叉搜索树的删除【※核心重点】(分析&代码演示)

分析

  • 首先查找元素是否在二叉搜索树中,如果不存在,则返回
  • 否则要删除的结点可能分下面四种情况:
  1. 要删除的结点无孩子结点
  2. 要删除的结点只有左孩子结点
  3. 要删除的结点只有右孩子结点
  4. 要删除的结点有左、右孩子结点
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构
  • 对上面四种情况整理后(1与2,3分别结合),剩下下面2种情况(直接删除,替换法),分出3种具体情况(直接删除占两种):
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构
  • 直接删除情况: 只有左/右/无孩子结点(无孩子,只有一个孩子)
    (双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点)
  • 情况1:被删除节点是其双亲节点的左节点,删除该结点且使被删除节点的双亲结点指向被删除节点的 左孩子 结点
  • 情况2:被删除节点是其双亲节点的右节点,删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构
  • 还要考虑结点为根结点情况:
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构
  • 替换法情况:【※核心难点】 (有两个孩子)
  • 情况3 :在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题
  • 分析:要 找到左子树的最大(右)结点,或者 右子树的最小(左)结点(下图演示中是找到左子树的最大结点)
  • 具体过程分析:
  1. 设置前后指针,留一个cur指针指向要删除结点,parent指针跟着LeftMax指针向下逐个移动
  2. 找到leftMax以后,交换其和cur的数值,(收完尾后,最后一步再将指针也一同转移)
  3. 要分为两种情况(如下图所示) (1) leftMax指针的左指针为空,(2) leftMax指针的左指针不为空
    (为什么不用讨论右指针呢?因为leftMax的右指针必定为空,否则leftMax会继续向下移动)
  4. 因为采用的是前后指针法,所以这时留下的后指针(parent)就对应指向leftMax的左/右结点
  5. 最后将cur指针指向leftMax,leftMax动不动无所谓
    【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23),YY滴 《数据结构》,YY 滴 《C++系列》,c++,开发语言,数据结构

代码演示

//删除操作
	bool Erase(const K& key)
	{
		Node* parent = nullptr;//后指针
		Node* cur = _root;//前指针

		while (cur)
		{
//通过二叉搜索树规则向下查找
			if (cur->_key < key)      
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
//直接删除情况:只有左/右/无孩子结点
//(双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点) 
			else // 找到了
			{
				 // 左为空      
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)//被删除节点是其双亲节点的右节点   
						{
							parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
						}
						else//被删除节点是其双亲节点的左节点  
						{
							parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点
						}
					}
				}
				// 右为空    
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}					
				} 

// 替换法情况:左右都不为空 
				else
				{
					// 找替代节点
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}

		return false;
	}

4.二叉搜索树的中序遍历(分析&代码演示)

分析

  • 中序遍历要从通过模板实例化的树中调用中序遍历函数
  • 需要传根结点指针,但是 根结点指针是在private域中,域外不能直接传一个根结点指针 ,所以要引入_InOrder函数,在二叉搜索树模板中 再次封装一层

代码演示

void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();  //需要传根结点指针,但是根结点指针是在private域中,域外不能直接传一个根结点指针,
	              //所以要引入_InOrder函数,在二叉搜索树模板中再次封装一层
}
//中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题,引入_InOrder函数
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

三.二叉搜索树的性能问题:需要AVL树…红黑树…

  • 插入和删除操作都必须先 查找,查找效率代表了二叉搜索树中各个操作的性能
  • 当二叉搜索树 退化为单支时,其效率为O(N),二叉搜索树的性能就失去了
  • 对二叉搜索树进行改进后,得到的AVL树红黑树效率为 Log(N)

四.二叉搜索树的完整实现代码演示

//结点模板
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

//二叉搜索树类模板
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:

//初始化列表
	BSTree()
		:_root(nullptr)
	{}
	

//查找操作
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

//插入操作
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}


//删除操作
	bool Erase(const K& key)
	{
		Node* parent = nullptr;//后指针
		Node* cur = _root;//前指针

		while (cur)
		{
//通过二叉搜索树规则向下查找
			if (cur->_key < key)      
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
//直接删除情况:只有左/右/无孩子结点
//(双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点) 
			else // 找到了
			{
				 // 左为空      
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)//被删除节点是其双亲节点的右节点   
						{
							parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
						}
						else//被删除节点是其双亲节点的左节点  
						{
							parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点
						}
					}
				}
				// 右为空    
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}					
				} 

// 替换法情况:左右都不为空 
				else
				{
					// 找替代节点
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}

				delete cur;
				return true;
			}
		}

		return false;
	}


//中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题,引入_InOrder函数
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}


private:
	Node* _root;
};


void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();

	t.Erase(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	t.Erase(3);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
	}
	t.InOrder();
}

五.进阶二叉树习题传送门

进阶二叉树习题传送门文章来源地址https://www.toymoban.com/news/detail-755349.html

到了这里,关于【C++&数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现&逐过程分析&代码演示&简练易懂](23)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】——单链表超详细介绍(独家介绍,小白必看!!!)

    被滑走别滑走 ,我这 一万字 的文章,写的真的很痛苦的,希望能得到 一点点支持 !!! 重点内容 和 易错点 都用 彩笔 标注了,干货满满,耐心看完,我真的真的有在 认真更新o(╥﹏╥)o 上一篇文章介绍完顺序表后,我们就要开始学习链表了,链表的种类有很多,比如说

    2024年02月02日
    浏览(40)
  • 【数据结构】顺序表---C语言版(数据结构开篇小菜,全网最详细!小白看一遍就学会!!!)

    停更了一个月限时返场啦😍从本篇文章开始就进入了我们数据结构的学习喽!本篇文章也是《数据结构与算法》 专栏的第一篇文章,本篇的内容是顺序表的学习,也是数据结构的开胃小菜,希望烙铁们可以理解消化哦🥰!!! 在我们学习 顺序表 之前呢,我们大家肯定会有

    2024年02月06日
    浏览(46)
  • 【数据结构】二叉树遍历的实现(超详细解析,小白必看系列)

    目录 一、前言 🍎为何使用链式二叉树   🍐何为链式二叉树  🍉二叉树的构建 💦创建二叉链结构 💦手动构建一颗树  🍓二叉树的遍历 (重点) 💦前序遍历  💦中序遍历  💦后续遍历  🍌二叉树的经典问题(重点) 💦二叉树节点个数  💦二叉树叶子节点的个数  💦

    2024年02月02日
    浏览(49)
  • 小白也能学会的链表 | C++ | 算法与数据结构 (新手村)

    本质:找到两个有序数据段中的第一个相同数据 解题:利用set的不重复性,首先把headA都塞到set中,再遍历headB找有没有已经出现在set中的节点即可。 注意! set的数据是ListNode* 不是 int。如果是int可能出现节点不同但是var相同的情况,而ListNode* 就不会。 时间复杂度:O(2n)

    2024年02月14日
    浏览(55)
  • 【数据结构——9大基础排序】一文掌握九大经典排序(配有详细图文说明!!!)

    算法基本思想:(从大到小排序) 在一个 非递减 的有序数组中,要新增一个元素 x ,有两个方法: 1.从数组的头部开始向后遍历,寻找 第一个比x 大 的元素 y ,从y元素开始的所有元素全部向后移动,最后将x元素插入数组。(×) 2.从数组的尾部开始向后向前遍历,寻找 第

    2024年02月08日
    浏览(45)
  • 全面理解链表数据结构:各种节点操作、做题技巧,易错点分析与题目清单(C++代码示例,不断更新)

    链表是一种线性数据结构,它包含的元素并不是物理上连续的,而是通过指针进行连接。链表中的每个元素通常由一个节点表示,每个节点包含一个数据元素和一个或多个链接(指针)。 链表的主要类型包括: 单向链表 (Singly Linked List):每个节点包含一个指向下一个节点

    2024年02月07日
    浏览(43)
  • 【数据结构】—搜索二叉树(C++实现,超详细!)

                                                           🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 :消えてしまいそうです—真夜中                                              

    2024年02月05日
    浏览(40)
  • 数据结构-双向链表(c++)超全超详细

    单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入,删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。 提示:以下是本篇文章正文内容,下面案

    2023年04月08日
    浏览(45)
  • C++数据封装以及定义结构的详细讲解鸭~

    名字:阿玥的小东东   博客主页:阿玥的小东东的博客_CSDN博客-pythonc++高级知识,过年必备,C/C++知识讲解领域博主 目录 定义结构 访问结构成员 结构作为函数参数

    2024年02月04日
    浏览(43)
  • 利用C++超详细解释数据结构中的链表

    链表(Linked List)是一种常见的数据结构,它可以动态地插入和删除元素,不需要像数组那样预先分配固定大小的内存。链表中的每个元素称为节点(Node),每个节点包含一个数据值和一个指向下一个节点的指针。本教学将涵盖以下知识点: 单向链表(Singly Linked List) 双向

    2024年02月04日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包