1. Toy模板网首页
  2. > Toy博客

〖数据结构〗一棵有点自律的树——搜索二叉树

10月前 作者：花想云 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了〖数据结构〗一棵有点自律的树——搜索二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

〖数据结构〗一棵有点自律的树——搜索二叉树

💐专栏导读

🌸作者简介：花想云，在读本科生一枚，致力于 C/C++、Linux 学习。

🌸本文收录于 C++系列，本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等，专为大学生打造全套 C++ 学习教程，持续更新！

🌸相关专栏推荐：C语言初阶系列 、C语言进阶系列 、数据结构与算法、Linux从入门到精通

💐文章导读

本章我们将认识一种新的二叉树——搜索二叉树。这棵树有个神奇的功能就是会对数据自动排序且有着非常高的查找效率。搜索二叉树作为set、map的基础结构，同样又是接下来将要学到的AVL树以及红黑树的实现基础非常值得我们去深入学习~

〖数据结构〗一棵有点自律的树——搜索二叉树

🌷搜索二叉树概念

二叉搜索树本质上也是一种二叉树，只不过多了一个约束规则——

若一棵二叉树不为空，则：

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
  • 它的左右子树也分别为搜索二叉树；

所以构建一个搜索二叉树，只需要在插入结点时满足约束规则即可。

🌷二叉搜索树的构建

与二叉树相同，二叉搜索树由一个个结点链接而成。每个结点包含三个成员——

  • _left（左孩子）；
  • _right（有孩子）；
  • _key（键值）；

所以首先定义一个BSTNode（Binary Search Tree简写）结构体——

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

	BSTreeNode(const K& key) // 构造函数
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

同样的，再定义一个搜索二叉树的类，即class BSTree——

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	// 成员函数的实现
	// 插入、删除、查找...
private:
	Node* _root = nullptr;
};

接着就是各种成员函数的实现了~

🌺查找操作

搜索二叉树的查找比较简单而且更容易帮助我们理解搜索二叉树的性质，所以先从查找入手。

〖数据结构〗一棵有点自律的树——搜索二叉树

以上图为例，倘若我们要查找 7，具体的思路是这样的——

  1. 7 < 8，因此去 8 的左子树去查找；
  2. 7 > 3，因此去 3 的右子树去查找；
  3. 7 > 6，因此去 6 的右子树去查找；
  4. 7 = 7，找到了，返回true；

于是我们试着着手实现一个Find函数。

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; // 找到返回true
	}
	return false; // 未找到返回false
}

🌺插入操作

理解了如何查找，插入也就非常简单。
〖数据结构〗一棵有点自律的树——搜索二叉树
还是以此图为例，倘若我们要插入 9 ，具体步骤为——

  1. 首先确定cur的位置，并随时更新parent；
  2. 最终，cur走到10的左节点的位置，即cur = nullptr，循环结束；
  3. 此时patent = Node*(10)；
  4. 最后一步，new一个结点Node*(key)并赋值给parent->_left即可。
bool Insert(const K& key)
{
	// 如果是第一次插入，直接new一个新结点给_root
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	
	Node* cur = _root; // cur用来定位插入的位置
	Node* parent = cur; // 记录parent的父亲
	
	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;
}

🌺删除操作

二叉搜索树的删除是最精华的部分。对与叶子节点，例如4、7、13，删除非常简单，只需将自身的位置替换为nullptr即可。

〖数据结构〗一棵有点自律的树——搜索二叉树
如果要删除14或者10，也是比较简单的，因为10的左右子树只有一方为nullptr（10的左子树为空），所以只需要载删除的时候让父结点接管自己不为空的子树即可。

倘若要删除6或者3，由于它们的左右子树都不为空，删除时无法将两个子树都交给父结点，情况就较为复杂。

所以此种情况，我们只能想办法请一个人来接替自己的位置，但是并不是谁来都能胜任这个位置的。这个接替者必须满足二叉搜索树的条件——左子树都比它小，右子树都比它大。那么这个接替者的人选只能有这两个——

  • 左子树的最大（最右）节点；
  • 或右子树的最小（最左）节点；

例如，倘若要删除3，此时有两种做法都可行——

  1. 用1替换3；
  2. 用7替换3；

综上所述，删除操作共分为一下几种情况——

  1. 左子树为空；
  2. 右子树为空；
  3. 左右子树都不为空 ；
  4. （左右子树都为空其实可以归并到1或2的情况中）；
bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = cur;
	while (cur)
	{
		// 找到值为key的结点
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else // 找到了
		{	
			// 删除
			if (cur->_left == nullptr) // 1.左子树为空
			{
				if (cur == _root) // 根节点的删除
				{
					_root = cur->_right;
					return true;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
					delete cur;
				}
			}
			else if (cur->_right == nullptr) // 2.右子树为空
			{
				if (cur == _root) // 根节点的删除
				{
					_root = cur->_left;
					return true;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
					delete cur;
				}
			}
			else // 左右子树都不为空
			{
				// 找左子树的最大结点 或者 右子树的最小结点
				Node* minRight = cur->_right;
				Node* pminRight = cur;

				while (minRight->_left)
				{
					pminRight = minRight;
					minRight = minRight->_left;
				}

				cur->_key = minRight->_key; // 替换
				
				if (pminRight->_left == minRight)
				{
					pminRight->_left = minRight->_right;
				}
				else
				{
					pminRight->_right = minRight->_right;
				}

				delete minRight;
			}
			return true;
		}
	}
	return false;
}

🌺遍历操作

最后，二叉搜索树的遍历非常简单，就是之前学习过的二叉树的中序遍历。

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

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

注：由于调用函数时C++封装的特性，需设计两个函数，InOrder接口对外提供，-—_InOrder不对外提供。

☘️测试

〖数据结构〗一棵有点自律的树——搜索二叉树

我们可以构建一棵这样的搜索二叉树，再对每一个结点进行删除操作，验证代码是否正确~

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

	for (auto e : a)
	{
		tree.EraseR(e);
		tree.InOrder();
	}
}

〖数据结构〗一棵有点自律的树——搜索二叉树

🏵️拓展——递归实现

对于搜索二叉树来说，上面实现的非递归版本是比递归版本更优的。此处的递归实现完全属于多余了，但是作为拓展内容看一看也未尝不可。

🍃递归查找

bool FindR(const K& key)
{
	return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
	if (root == nullptr)
		return false;
	if (root->_key == key)
		return true;
	if (root->_key > key)
		_FindR(root->_left, key);
	else
		_FindR(root->_right, key);
}

🍃递归插入

bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

bool _InsertR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}
	if (root->_key < key)
		return _InsertR(root->_right, key);
	else if (root->_key > key)
		return _InsertR(root->_left, key);
	else
		return false;
}

🍃递归删除

bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

bool _EraseR(Node*& root,const K& key)
{
	if (root == nullptr)
		return false;
	if (root->_key < key)
		return _EraseR(root->_right, key);
	else if (root->_key > key)
		return _EraseR(root->_left, key);
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
			root = root->_right;
		else if (root->_right == nullptr)
			root = root->_left;
		else
		{
			Node* maxLeft = root->_left;
			while (maxLeft->_right)
				maxLeft = maxLeft->_right;
			std::swap(root->_key, maxLeft->_key);
			return _EraseR(root->_left, key);
		}
		delete del;
		return true;
	}
}

❄️完整源码

🐙非递归版

#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = cur;

		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 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 Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = cur;
		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;
						return true;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
						delete cur;
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
						return true;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
						delete cur;
					}
				}
				else
				{
					// 找左子树的最大结点 或者 右子树的最小结点
					Node* minRight = cur->_right;
					Node* pminRight = cur;

					while (minRight->_left)
					{
						pminRight = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_key;
					if (pminRight->_left == minRight)
					{
						pminRight->_left = minRight->_right;
					}
					else
					{
						pminRight->_right = minRight->_right;
					}

					delete minRight;
				}
				return true;
			}
		}
		return false;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
protected:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

🐌递归版本

#pragma once
#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
protected:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key == key)
			return true;
		if (root->_key > key)
			_FindR(root->_left, key);
		else
			_FindR(root->_right, key);
	}
	bool _EraseR(Node*& root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
			return _EraseR(root->_right, key);
		else if (root->_key > key)
			return _EraseR(root->_left, key);
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
				root = root->_right;
			else if (root->_right == nullptr)
				root = root->_left;
			else
			{
				Node* maxLeft = root->_left;
				while (maxLeft->_right)
					maxLeft = maxLeft->_right;
				std::swap(root->_key, maxLeft->_key);
				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left, key);
		else
			return false;
	}
	
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

〖数据结构〗一棵有点自律的树——搜索二叉树

⭐抽奖活动⭐

抽奖文章链接——Spring Cloud——演进与应用的分布式系统开发利器（文末赠书3册）

⭐感谢赞助⭐

618，清华社 IT BOOK 多得图书活动开始啦！活动时间为2023年6月7日至6月18日，清华社为您精选多款高分好书，涵盖了C++、Java、Python、前端、后端、数据库、算法与机器学习等多个IT开发领域，适合不同层次的读者。全场5折，扫码领券更有优惠哦！

优惠购书请戳这里

〖数据结构〗一棵有点自律的树——搜索二叉树文章来源地址https://www.toymoban.com/news/detail-479944.html

到了这里，关于〖数据结构〗一棵有点自律的树——搜索二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【gdb调试】在ubuntu环境使用gdb调试一棵四层二叉树的数据结构详解

    【gdb调试】在ubuntu环境使用gdb调试一棵四层二叉树的数据结构详解

    目录 🌞1. 整体思路 🌞2. 准备内容 🌼2.1 配置.c文件 🌼2.2 准备测试程序 🌼2.3 GDB调试基础 🌞3. GDB调试四层二叉树 🌼3.1 测试程序分析 🌼3.2 gdb分析 🌻1. 设置断点 🌻2. 启动程序并执行到断点处 🌻3. 打印变量的值 🌻4. 单步执行 s 进入buildTree函数内部 a. 第一层：根节点赋

    2024年04月17日
    浏览(27)
  • 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀，今天小雅兰的内容仍然是二叉树和Leetcode每日一题，下面，就让我们进入二叉树的世界吧！！！ 这个题目需要重新定义一个函数，函数参数需要有左子树和右子树，题目所给定的函数无法解决问题。 每个不为空的结点，都可以认为是一棵子树的根 

    2024年02月16日
    浏览(46)
  • 二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀，今天继续数据结构与算法专栏中的二叉树，下面，让我们进入二叉树的世界吧！！！ 二叉树（上）——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 数据结构 | 搜索和排序——搜索

    数据结构 | 搜索和排序——搜索

    目录 一、顺序搜索 二、分析顺序搜索算法 三、二分搜索 四、分析二分搜索算法 五、散列 5.1 散列函数 5.2 处理冲突 5.3 实现映射抽象数据类型 搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回True或False，分别表示元素是否存在。有时，可以修改搜索过

    2024年02月14日
    浏览(38)
  • 【数据结构】6.搜索树

    【数据结构】6.搜索树

    二叉搜索树：  一棵非空的二叉搜索树每个元素都有一个，并且任意两个元素的不同，所有都是唯一的 根节点的左子树小于根节点的 根节点的右子树大于根节点的 左右子树也是二叉搜索树 索引二叉搜索树： 源于普通的二叉搜索树，在每个

    2024年02月08日
    浏览(36)

  • 数据结构-图搜索算法详解

    图搜索算法是数据结构和算法学科中的一个重要领域，它们用于在图中搜索顶点（节点）和边（连接节点的线）。图可以是有向的（边有方向）或无向的（边没有方向）。图搜索算法主要用于解决如路径查找、网络流分析等问题。下面详细介绍几种常见的图搜索算法。 深度优

    2024年04月28日
    浏览(34)
  • [数据结构]-二叉搜索树

    [数据结构]-二叉搜索树

    前言 作者 ： 小蜗牛向前冲 名言 ： 我可以接受失败，但我不能接受放弃   如果觉的博主的文章还不错的话，还请 点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。 目录 一、二叉搜索树的基本知识 1、什么是二叉搜索树 2、二叉搜索树的性能

    2024年02月08日
    浏览(46)
  • 数据结构——二叉搜索树

    数据结构——二叉搜索树

    本章代码:二叉搜索树 二叉搜索树又叫二叉排序树，它具有以下性质： 若左子树不为空，则左子树上所有结点的值都小于根结点的值 若右子树不为空，则右子树上所有结点的值都大于根结点的值 它的左右子树也分别为二叉搜索树 这个结构的时间复杂度为一般人会以为是 O(

    2024年02月12日
    浏览(42)
  • 数据结构---二叉搜索树

    数据结构---二叉搜索树

    二叉搜索树(Binary Search Tree 简称BST)又称二叉排序树，是一种二叉树的特殊形式，它在每个节点上存储的键值满足以下性质： 若它的左子树不为空，则左子树上的所有节点的 值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也

    2024年02月07日
    浏览(42)
  • 【数据结构】二叉搜索树

    【数据结构】二叉搜索树

    二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树： 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 两种情况： 树为空，则

    2024年01月19日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包