当前位置： 首页 > article >正文

数据结构——“二叉搜索树”

article 2024/11/15 12:30:29

        二叉搜索树是一个很重要的数据结构，它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是O(n)，最好是O(logn)。接下来看一看它的接口函数的实现。

        为了使用方便，这里采用模版的方式：

一、节点

template <class K>
struct BSnode
{
	BSnode(K key)
		:_key(key)
	{}
	K _key;
	BSnode* _left = nullptr;
	BSnode* _right = nullptr;
};

        _key用来储存数据，_left和_right用来储存左子树和右子树的节点。

二、搜索树的类的定义

template <class K>
class BSTree
{
private:
	using Node = BSnode<K>;
	Node* _root = nullptr;
};

        这里typedef了BSnode<K>为Node的类型，方便使用。并创建了根节点，缺省值为空指针。

三、搜索树的插入

        搜索树的结构是左子树所有节点的值小于等于根结点的值，右子树所有节点的值大于等于根节点的值。在这里我不考虑等于的情况，即一棵树中不允许出现相同的值。代码如下：

	//搜索树的插入
	bool Insert(K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		if (cur == nullptr)
		{
			_root = new Node(key);
		}
		else
		{
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			if (key > parent->_key)//插入的值大于父亲节点，那么就需要在父亲节点的右边插入
			{
				parent->_right = new Node(key);
			}
			else//插入的值小于父亲节点，那么就需要在父亲节点的左边插入
			{
				parent->_left = new Node(key);
			}
		}
		return true;
	}

        代码大体情况如下：

        1.第一次插入数据的时候，根节点指向空，需要单独讨论。

        2.根节点不为空，那么就根据搜索树的特点找到最后插入的位置，申请新节点，连接新节点。

        3.找不到插入的位置，即插入的数据已经存在，返回false。

四、搜索树的查找

	//搜索树的查找
	Node* Find(const K& key)
	{
		assert(_root);
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key <  key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

        这段代码是根据搜索树的特点进行查找（搜索的值大于根，那么去右子树查找，小于则去左子树查找），倘若找到，返回该节点指针，找不到，返回空指针。

五、搜索树的删除

        搜索树的删除偏向复杂，在我写出的代码中大致分为以下几点：

        1.删除的数据在叶子节点上。

        2.删除的节点不在叶子节点上，但是它的左右节点至少有一个是空。

        3.删除的节点不在叶子节点上，且左右子树都不为空。

        4.删除的节点在根节点，根节点至少有一个为空。

通过总结可以精简以上条件：

        1.删除的节点的左右节点至少有一个为空。

        2.删除的节点的左右节点都不为空。

代码如下：

	//搜索二叉树的删除
	bool Erase(const K& key)
	{
		assert(_root);
		//先找到要删除的节点
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				break;
			}
		}

		//找不到要删除的数据，返回false
		if (cur == nullptr)return false;
		//找到了
		
//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”
		if (cur->_left == nullptr || cur->_right == nullptr)
		{
			//该节点是根，且且根节点至少一个子树为空
			if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 
			{
				_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;
				delete cur;
			}
			//该节点是左孩子
			else if (cur == parent->_left)
			{
				//左节点为空
				if (cur->_left == nullptr && cur->_right != nullptr)
				{
					parent->_left = cur->_right;
				}
				//右节点为空
				else if(cur->_left != nullptr && cur->_right == nullptr)
				{
					parent->_left = cur->_left;
				}
				//左右节点均为空
				else
				{
					parent->_left = nullptr;
				}
				
				//释放资源
				delete cur;
			}
			//该节点是右孩子
			else if (cur == parent->_right)
			{
				//左节点为空
				if (cur->_left == nullptr && cur->_right != nullptr)
				{
					parent->_right = cur->_right;
				}
				//右节点为空
				else if (cur->_left != nullptr && cur->_right == nullptr)
				{
					parent->_right = cur->_left;
				}
				//左右节点均为空
				else
				{
					parent->_right = nullptr;
				}

				//释放资源
				delete cur;
			}
		
		}
//处理“该节点的左右孩子均不为空”
		else
		{
			//找到左节点的最大值
			Node* Fparent = cur;
			Node* Fcur = cur->_left;
			


			while (Fcur ->_right)
			{
				Fparent = Fcur;
				Fcur = Fcur->_right;
			}
			//交换节点的值
			cur->_key = Fcur->_key;
			//Fcur的左边有数据
			if (Fcur->_left)
			{
				Fparent->_right = Fcur->_left;
				delete Fcur;
			}
			//Fcur的左边没有数据
			else
			{
				
				if(Fcur == Fparent->_left)
				{
					Fparent->_left = nullptr;
				}
				else
				{
					Fparent->_right = nullptr;
				}
				delete Fcur;
			}

		}
		
		return true;
	}

        首先是先要找到删除的数据，若找不到，返回false，若找到，那么进行下一步：

找到后还有如下情况：

        1.删除的节点的左右节点至少有一个为空。

        对应代码：

//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”
		if (cur->_left == nullptr || cur->_right == nullptr)
		{
			//该节点是根，且且根节点至少一个子树为空
			if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 
			{
				_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;
				delete cur;
			}
			//该节点是左孩子
			else if (cur == parent->_left)
			{
				//左节点为空
				if (cur->_left == nullptr && cur->_right != nullptr)
				{
					parent->_left = cur->_right;
				}
				//右节点为空
				else if(cur->_left != nullptr && cur->_right == nullptr)
				{
					parent->_left = cur->_left;
				}
				//左右节点均为空
				else
				{
					parent->_left = nullptr;
				}
				
				//释放资源
				delete cur;
			}
			//该节点是右孩子
			else if (cur == parent->_right)
			{
				//左节点为空
				if (cur->_left == nullptr && cur->_right != nullptr)
				{
					parent->_right = cur->_right;
				}
				//右节点为空
				else if (cur->_left != nullptr && cur->_right == nullptr)
				{
					parent->_right = cur->_left;
				}
				//左右节点均为空
				else
				{
					parent->_right = nullptr;
				}

				//释放资源
				delete cur;
			}
		
		}

        原理：由于删除的节点左右子树至少有一个为空，那么就可以让父节点继承被删除节点的非空节点。继承后，删除该节点。如果被删除的节点的左右子树都为空，即被删除的节点是叶子节点，那么就可以直接删除叶子节点，然后将父节点指向空。

        以上代码分别对删除的节点是左子树还是右子树的情况下，删除的节点是否有左子树，是否有右子树，还是左右子树都没有进行讨论，涵盖所有情况。值得注意的是，当搜索树呈现链状的时候，如果删除的是根节点，此时的父节点是空，不能进行访问，那么需要在这里单独讨论。将根节点移动到有数据的那个子节点。

2.删除的节点的左右节点都不为空。

        对应代码：

//处理“该节点的左右孩子均不为空”
		else
		{
			//找到左节点的最大值
			Node* Fparent = cur;
			Node* Fcur = cur->_left;
			while (Fcur ->_right)
			{
				Fparent = Fcur;
				Fcur = Fcur->_right;
			}
			//交换节点的值
			cur->_key = Fcur->_key;
			//Fcur的左边有数据
			if (Fcur->_left)
			{
				Fparent->_right = Fcur->_left;
				delete Fcur;
			}
			//Fcur的左边没有数据
			else
			{
				
				if(Fcur == Fparent->_left)
				{
					Fparent->_left = nullptr;
				}
				else
				{
					Fparent->_right = nullptr;
				}
				delete Fcur;
			}

		}

        第二种情况就不能直接进行交换。因为父节点没有多余的指针指向被删除节点的左右节点。那么在这里的思想是找到一个比被删除的节点的左孩子大，右孩子小。符合条件的是：左子树的最大值，或者右子树的最小值。找到之后交换节点值。但是还是需要注意的是，找到最大值以后，分为两种情况：

        a.最大值的左边为空。

        b.最大值的左边不为空。

那么进行讨论：比如删除的数据是8。

a.最大值的左边为空：

这个条件下可以直接交换删除

b.最大值的左边不为空：

        这种情况下就需要将父节点的右节点（最大值的位置）指向最大值的左节点。

在这段代码中：

			//找到左节点的最大值
			Node* Fparent = cur;
			Node* Fcur = cur->_left;
			while (Fcur ->_right)
			{
				Fparent = Fcur;
				Fcur = Fcur->_right;
			}

        Node* Fparent = cur;的目的是避免这种情况下，空指针解引用的问题：删除的数据是3：

倘若Fparent 为空

        此时Fcur已经为叶子节点（已经为3的左子树的最大值），while循环不会进而以下代码会对Fparent解引用，造成访问空指针的错误。如果将Fparent复制为cur，那么从一开始，Fparent就是Fcur的父节点，既不违反逻辑，也解决了问题。

        因为此时1在父节点的左边，所以综上所述，再删除节点的同时也是需要判断被删除的节点是左节点还是右节点。

示例：

int main()
{
	BSTree<int> tree;

	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (auto f : a)
	{
		tree.Insert(f);
	}


	for (auto f : a)
	{
		tree.Erase(f);
		tree.InTraversal();
		cout << endl;
	}

	return 0;
}

结果（中序遍历）：


http://www.kler.cn/a/308107.html

相关文章：

  • 【IC每日一题：IC常用模块--RR/handshake/gray2bin】
  • Rocky、Almalinux、CentOS、Ubuntu和Debian系统初始化脚本v9版
  • SQL 中 BETWEEN AND 用于字符串的理解
  • 传奇996_21——龙岭事件
  • kafka面试题解答（四）
  • Python数据类型（一）：bool布尔类型
  • Python和R均方根误差平均绝对误差算法模型
  • 监听RabbitMQ，向Elasticsearch 创建索引
  • python selenium网页操作
  • C++笔记---二叉搜索树
  • 动手学深度学习（pytorch）学习记录31-批量规范化(batch normalization)[学习记录]
  • C++基础面试题 | C++中的构造函数可以是虚函数吗？ C++中的析构函数一定要是虚函数吗？
  • SpringBoot 消息队列RabbitMQ消息的可靠性 配置连接重试 生产者重连
  • 医学数据分析实训 项目三 关联规则分析作业--在线购物车分析--痹症方剂用药规律分析
  • 科技赋能司法：易保全如何重塑法律文书签署与庭审流程
  • yjs07——numpy数组的使用
  • 【Linux】-基本指令（上）
  • 7-16 一元多项式求导(vector)
  • Linux - iptables防火墙
  • 安全、稳定、高速的跨国文件传输系统
  • Vue3 : ref 与 reactive
  • 【DataSophon】Yarn配置历史服务器JobHistory和Spark集成historyServer
  • 【C++】list常见用法
  • 数据库基础（MySQL）
  • 【C++】——string类的模拟实现
  • 【网络】DNS，域名解析系统