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

【数据结构】搜索二叉树

article 2025/1/22 1:38:17

二叉搜索树

二叉树的博客

在之前的数据结构的文章中已经基本对二叉树有一定的了解，二叉搜索树也是一种数据结构，下面将对二叉搜索树进行讲解。

二叉搜索树的概念

        二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有下面性质的二叉树：

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

​

​

​

二叉搜索树的特点是搜索数据比较快，最多高度次就可以找到所值，其高度最大就是O(N)

二叉搜索树的实现过程

基本框架

  • 需要有一个struct的类（struct的类默认公开）来包含一个节点的所有特性，包括其可以指向左子树、右子树以及其包含的数据。
  • 然后使用class的类来对这棵二叉搜索树进行封装。
template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

template<class K>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:

private:
	Node* _root;
};

初始化二叉树：

	//初始化节点
	BSTree()
		:_root(nullptr)
	{}

二叉搜索树的插入

插入过程：

  • 当树为空的时候，直接新增节点，赋值给root指针。
  • 树不为空，按二叉搜索树的性质查找插入位置，插入新节点。
//插入数据
bool insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	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 (cur->_key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

搜索二叉树的打印（使用中序遍历）

        在这段代码中，使用_root作为参数传递给_InOrder函数，而不是直接在_InOrder函数中使用__root，主要是为了增加代码的灵活性和可复用性。

这样做的好处是，_InOrder函数可以处理不同的二叉树，而不仅仅局限于某个特定的二叉树对象。通过将二叉树的根节点作为参数传递给_InOrder函数，就可以对任意给定的二叉树进行中序遍历。

如果直接在_InOrder函数中使用_root，那么_InOrder函数就只能操作类内部固定的_root成员变量所代表的二叉树。而通过参数传递的方式，可以在需要的时候将不同的二叉树根节点传递给_InOrder函数，使其能够对各种不同的二叉树进行操作，提高了函数的通用性。

	//二叉树的升序打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

二查搜索树的查找

  1. 从根开始查找，如果比根小走左路，比根大走右路。
  2. 最多查找高度次，如果没找到则不存在。

二叉搜索树的删除（难点）

        首先需要查找元素中是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可以分为下面四种情况：

  1. 要删除的节点无孩子节点。
  2. 要删除的节点只有左孩子节点。
  3. 要删除的节点只有右孩子节点。
  4. 要删除的节点有左、右孩子节点。

总结下来，实际中真正要删除的情况只有三种：

  1.  删除该节点且使被删除节点的双亲结点指向被删除节点的左孩子节点——直接删除。
  2. 删除该节点且使被删除节点的双亲结点指向被删除节点的右孩子节点——直接删除。
  3. 在它的右子树中寻找中序下的第一个节点（数值最小）或者在它的左子树中寻找中序前的最后一个节点（数值最大），用它的值填补到被删除节点中，再来处理该节点的删除问题【替换法】。 

再进行缩减就是：

  1. 没有孩子或者只有一个孩子，进行托孤。
  2. 有俩个孩子进行替换。

	//搜索二叉树的删除
	bool Erase(const K& key)
	{
		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
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
				}
				else if(cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				else
				{
					//替换法
					Node* LeftMax = _root->_left;
					Node* parent = _root;
					while (LeftMax->_right)
					{
						parent = LeftMax;
						LeftMax = LeftMax->_right;
					}
					swap(LeftMax->_key, cur->_key);

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

					cur = LeftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

分析该代码：

二叉树的递归实现

在递归实现的过程中，唯一需要注意的地方是使用了指针引用，这是因为引用不能改变指向，但是在递归函数的过程中都会重新定义引用。

递归升序打印

	//二叉树的升序打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

递归查找

	//查找
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
private:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else
		{
			return true;
		}
	}

递归插入

	//插入
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
private:
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
	}

递归删除

	//删除
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else if(root->_key < key)
		{
			return _EraseR(root->_right, 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;
				}
				swap(root->_key, MaxLeft->_key);

				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}
	}

二叉树完整代码展示

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

template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

template<class K>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//初始化节点
	BSTree()
		:_root(nullptr)
	{}
	//插入数据
	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		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 (cur->_key > parent->_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->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	//搜索二叉树的删除
	bool Erase(const K& key)
	{
		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
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
				}
				else if(cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				else
				{
					//替换法
					Node* LeftMax = _root->_left;
					Node* parent = _root;
					while (LeftMax->_right)
					{
						parent = LeftMax;
						LeftMax = LeftMax->_right;
					}
					swap(LeftMax->_key, cur->_key);

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

					cur = LeftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

	//二叉树的升序打印
	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);
	}
private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else if(root->_key < key)
		{
			return _EraseR(root->_right, 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;
				}
				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->_left, key);
		}
		else if (root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
	}

	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else
		{
			return true;
		}
	}

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

二叉树的应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。K模型可以快速判断在不在的场景，之前模拟实现的就是K模型。

  • 应用1：门禁系统。
  • 应用2：小区车辆出入系统（是否允许进入）。
  • 应用3：判断单词是否正确。

2.KV模型：每一个关键码key，都会对应一个value的值，即< key,value >。KV模型可以通过一个值快速找到另外一个值。

  • 应用1：手机号码查询快递。
  • 应用2：商城车辆出入系统（记录实际）。
  • 应用3：高铁实名制车票系统。
  • 应用4：英汉词典的中英文对应关系。

KV模型代码展示：

#include<iostream>

using namespace std;

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

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

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

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

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

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

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

	private:
		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;

				// 1、左为空
				// 2、右为空
				// 3、左右都不为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}

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

					return _EraseR(root->_left, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return true;
			}

			if (root->_key < key)
			{
				return _InsertR(root->_right, key, value);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key, value);
			}
			else
			{
				return false;
			}
		}

		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return root;
			}
		}

		void _InOrder(Node* root)
		{
			if (root == NULL)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

	void TestBSTree1()
	{
		//BSTree<string, Date> carTree;
		BSTree<string, string> dict;
		dict.InsertR("insert", "插入");
		dict.InsertR("sort", "排序");
		dict.InsertR("right", "右边");
		dict.InsertR("date", "日期");

		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.FindR(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词" << endl;
			}
		}
	}

	void TestBSTree2()
	{
		// 统计水果出现的次数
		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			auto ret = countTree.FindR(str);
			if (ret == nullptr)
			{
				countTree.InsertR(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}

		countTree.InOrder();
	}
}

二叉树的性能分析

插入和删除都必须先查找，查找效率代表了二叉搜索树的各个操作的性能。

        对于n个节点的二叉搜索树，若是每一个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较的次数越多。

        但是如果同一组数据的插入次序不同，可能得到不同结构的二叉搜索树。

最优的情况是：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：logN

最差的情况是：二叉搜索树退化成单支树（或者类似单支），其平均的比较次数为N。

        使用有序数组进行二分查找的时候，其缺点是插入与删除效率不高；

        使用搜索二叉树进行二分查找的时候，其可以很好地利用其特性进行查找、插入、删除、排序等操作，但是搜索二叉树的唯一缺点就是下限无保障（一条光杆树）。

        所以在后续的C++文章中会介绍AVL树、红黑树、B树来解决这个问题。


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

相关文章：

  • 游戏AI，让AI 玩游戏有什么作用？
  • linux如何并行执行命令
  • Windows电脑安装USB Redirector并实现内外网跨网USB共享通信访问
  • 数据结构-队列
  • 麦田物语学习笔记:场景切换淡入淡出和动态UI显示
  • 每日一刷——1.20——准备蓝桥杯
  • 【有啥问啥】什么是端到端（End-to-End）？
  • 【AI大模型Agent探索】深入探索实践 Qwen-Agent 的 Function Calling
  • 【Linux】Linux入门（4）其他常用指令
  • 基于Docker的Kafka分布式集群
  • leetcode——和为K的子数组（java）
  • 【配置环境】VS Code中JavaScript环境搭建
  • Ubuntu22.04系统切换内核版本
  • 【论文投稿】探秘嵌入式硬件设计：从原理到代码实战
  • 计算机视觉模型的未来：视觉语言模型
  • java快速导出word文档
  • 小结：OSPF协议的工作原理
  • Linux探秘坊-------3.开发工具详解（2）
  • Spring Event和MQ的区别和使用场景
  • Java JDK17 API 离线文档下载
  • 【深度学习项目】语义分割-DeepLab网络（DeepLabV3介绍、基于Pytorch实现DeepLabV3网络）
  • ubuntu下，模仿安装vllm,仅记录
  • android如何将字符串\u83b7\u53d6\u6210\u529f转换成中文
  • Mac安装配置使用nginx的一系列问题
  • 一文大白话讲清楚webpack基本使用——3——图像相关loader的配置和使用
  • 摘录人工智能面试笔试题汇总