【C++】二叉搜索树

用户11719958

发布于 2025-12-30 14:55:22

1850

1，二叉搜索树的概念

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

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值。 • 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值。 • 它的左右⼦树也分别为二叉搜索树

示例：

2，二叉搜索树性能分析

N为节点个数最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其高度为： O(logN) 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单支)，近似于链表，其高度为： O(N）

所以，综合而言二叉搜索树增删查改时间复杂度为： O(N) 。我们知道数组的增删查改的效率也是O(N),因此这个二叉搜索树的效率是无法满足我们需求的。在后面的文章中，会介绍二叉搜索树的变形，平衡二叉搜索树AVL和红黑树，才能适⽤于我们在内存中存储和搜索数据。

•另外需要说明的是，⼆分查找也可以实现 O(logN) 级别的查找效率，但是⼆分查找有两⼤缺陷：

1. 需要存储在⽀持下标随机访问的结构中，并且有序。 2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

3，二叉搜索树的代码实现

3.1，大致结构

//二叉搜索树的节点
template<class K>
class BSTNode
{
public:
	BSTNode(const K& data=K())
		:_key(data)
		,_left(nullptr)
		,_right(nullptr)
	{}
	K _key;
	BSTNode<K>* _left;//左孩子
	BSTNode<K>* _right;//右孩子
};

//二叉搜索树
template<class K>
class BSTree
{
public:
	typedef BSTNode<K> Node;
    //插入的实现...
    //查找的实现...
    //删除的实现...
private:
	Node* _root = nullptr;//根
};

3.2，二叉搜索树的插入

插⼊的具体过程如下：

1. 树为空，则直接新增结点，赋值给root指针

2. 树不空，按⼆叉搜索树性质，插⼊值比当前结点⼤往右走，插⼊值比当前结点小往左走，找到空位置，插⼊新结点。

3. 如果支持插⼊相等的值，插⼊值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左走）

代码实现（含注释）：

//插入
bool Insert(const K& key)
{
	//根为空，直接增加新节点，赋值给根
	if (_root ==nullptr)
	{
		_root = new Node(key);
		return true;
	}
	//从根位置开始比较
	Node* cur = _root;
	//记录比较过程中的父节点
	Node* parent = nullptr;
	while (cur)
	{
		//大于当前节点，进入右子树
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		//小于当前节点，进入左子树
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//不支持插入相等的值
		else
		{
			return false;
		}
	}
	//循环结束后，cur找到插入的位置
	cur = new Node(key);
	//与父节点比较，插入父节点的左还是右
	if (parent->_key > key)
		parent->_left = cur;
	else
		parent->_right = cur;
	return true;
}

3.3，二叉搜索树的遍历

二叉搜索树的遍历一般进行的是中序遍历。由于二叉搜索树的性质：左子树小于根，右子树大于根，所以中序遍历的结果是一个有序（升序）的。

实际上就是一个二叉树的中序遍历。

代码实现：

因为根节点为私有成员，不能再外面直接访问，所以我们可以套一层。

//中序遍历
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}
void _InOrder(Node* _root)
{
	if (_root == nullptr)
		return;
	_InOrder(_root->_left);
	cout << _root->_key << " ";
	_InOrder(_root->_right);
}

3.4，二叉搜索树的查找

1. 从根开始⽐较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。

2. 最多查找高度次，走到到空，还没找到，这个值不存在。

3. 如果不支持插⼊相等的值，找到x即可返回

4. 如果支持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。

代码实现：

//查找
bool find(const K& key)
{
	if (_root == nullptr)
		return false;
	//这里的parent其实没用，这里是复用了插入的逻辑
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
		    //找到了
			return true;
		}
	}
	return false;
}

3.5，二叉搜索树的删除

首先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

1. 要删除结点N左右孩子均为空 2. 要删除的结点N左孩子为空，右孩子结点不为空 3. 要删除的结点N右孩子为空，左孩子结点不为空 4. 要删除的结点N左右孩子结点均不为空

其实对于第一种情况，它的左右孩子均为空，我们可以将它看成是情况2或者情况3。

例如：看成是情况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
		{
			//删除
			//情况1:左为空
			if (cur->_left == nullptr)
			{
				//如果要删除的节点为根节点，它的左子树为空
				//让右子树成为新的根节点
				if (cur == _root)
					_root = cur->_right;
				else
				{
					//判断要删除的节点cur是父亲节点的左孩子还是右孩子
					//是左孩子，让cur的孩子成为父亲节点的左孩子
					//是右孩子，让cur的孩子成为父亲节点的右孩子
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}
				delete cur;
			}
			//情况2:右为空
			else if (cur->_right == nullptr)
			{
				//如果要删除的节点为根节点，它的右子树为空
				//让左子树成为新的根节点
				if (cur == _root)
					_root = cur->_left;
				else
				{
					//判断要删除的节点cur是父亲节点的左孩子还是右孩子
					//是左孩子，让cur的孩子成为父亲节点的左孩子
					//是右孩子，让cur的孩子成为父亲节点的右孩子
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}
				delete cur;
			}
			else//情况3:左右不为空,替换法
			{
				//replace找到替换的节点
				//replaceparent记录替换节点的父亲节点,在删除replace节点时会用到
				Node* replaceparent = cur;
				Node* replace = cur->_right;
                //找右子树的最左节点
				while (replace->_left)
				{
					replaceparent = replace;
					replace = replace->_left;
				}
				//交换节点
				cur->_key = replace->_key;

				//替换后，用前面两种情况的方式删除替换节点replace
				//让替换节点的左孩子或者右孩子连接
				//然后删除替换节点
				if (replaceparent->_left == replace)
					replaceparent->_left = replace->_right;
				else
					replaceparent->_right = replace->_right;

				delete replace;
			}
			//return true;
		}
	}
	return false;
}

3.6，二叉搜索树的拷贝构造

同样，_root为私有成员变量，不能再外面访问，所以套一层，在类里面就可以使用了。

   BSTree() = default;//强制生成构造函数 	
   //拷贝构造
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newnode = new Node(root->_key);
		newnode->_left = copy(root->_left);
		newnode->_right = copy(root->_right);

		return newnode;
	}
	BSTree(const BSTree& t)
	{
		_root = copy(t._root);
	}

3.7，二叉搜索树的析构函数

//析构
//后序
void Destory(Node* root)
{
	if (root == nullptr)
		return;
	Destory(root->_left);
	Destory(root->_right);
	delete root;
}
~BSTree()
{
	Destory(_root);
}

3.8，赋值重载函数

//赋值
BSTree& operator=(BSTree t)
{
	swap(_root, t._root);
	return *this;
}

3.9，代码总体

//二叉搜索树的节点
template<class K>
class BSTNode
{
public:
	BSTNode(const K& data=K())
		:_key(data)
		,_left(nullptr)
		,_right(nullptr)
	{}
	K _key;
	BSTNode<K>* _left;//左孩子
	BSTNode<K>* _right;//右孩子
};


//二叉搜索树
template<class K>
class BSTree
{
public:
	//using Node = BSTNode<K>;
	typedef BSTNode<K> Node;
	//插入
	bool Insert(const K& key)
	{
		//根为空，直接增加新节点，赋值给根
		if (_root ==nullptr)
		{
			_root = new Node(key);
			return true;
		}
		//从根位置开始比较
		Node* cur = _root;
		//记录比较过程中的父节点
		Node* parent = nullptr;
		while (cur)
		{
			//大于当前节点，进入右子树
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			//小于当前节点，进入左子树
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			//不支持插入相等的值
			else
			{
				return false;
			}
		}
		//循环结束后，cur找到插入的位置
		cur = new Node(key);
		//与父节点比较，插入父节点的左还是右
		if (parent->_key > key)
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}
	//查找
	bool find(const K& key)
	{
		if (_root == nullptr)
			return false;
		//这里的parent其实没用，这里是复用了插入的逻辑
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			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
			{
				//删除
				//情况1:左为空
				if (cur->_left == nullptr)
				{
					//如果要删除的节点为根节点，它的左子树为空
					//让右子树成为新的根节点
					if (cur == _root)
						_root = cur->_right;
					else
					{
						//判断要删除的节点cur是父亲节点的左孩子还是右孩子
						//是左孩子，让cur的孩子成为父亲节点的左孩子
						//是右孩子，让cur的孩子成为父亲节点的右孩子
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
					delete cur;
				}
				//情况2:右为空
				else if (cur->_right == nullptr)
				{
					//如果要删除的节点为根节点，它的右子树为空
					//让左子树成为新的根节点
					if (cur == _root)
						_root = cur->_left;
					else
					{
						//判断要删除的节点cur是父亲节点的左孩子还是右孩子
						//是左孩子，让cur的孩子成为父亲节点的左孩子
						//是右孩子，让cur的孩子成为父亲节点的右孩子
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					delete cur;
				}
				else//情况3:左右不为空,替换法
				{
					//replace找到替换的节点
					//replaceparent记录替换节点的父亲节点,在删除replace节点时会用到
					Node* replaceparent = cur;
					Node* replace = cur->_right;
					//找右子树的最左节点
					while (replace->_left)
					{
						replaceparent = replace;
						replace = replace->_left;
					}
					//交换节点
					cur->_key = replace->_key;

					//替换后，用前面两种情况的方式删除替换节点replace
					//让替换节点的左孩子或者右孩子连接
					//然后删除替换节点
					if (replaceparent->_left == replace)
						replaceparent->_left = replace->_right;
					else
						replaceparent->_right = replace->_right;

					delete replace;
				}
				//return true;
			}
		}
		return false;
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	//赋值
	BSTree& operator=(BSTree t)
	{
		swap(_root, t._root);
		return *this;
	}
	BSTree() = default;
	//拷贝构造
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newnode = new Node(root->_key);
		newnode->_left = copy(root->_left);
		newnode->_right = copy(root->_right);

		return newnode;
	}
	BSTree(const BSTree& t)
	{
		_root = copy(t._root);
	}
	//析构
	void Destory(Node* root)
	{
		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}
	~BSTree()
	{
		Destory(_root);
	}
private:
	void _InOrder(Node* _root)
	{
		if (_root == nullptr)
			return;
		_InOrder(_root->_left);
		cout << _root->_key << " ";
		_InOrder(_root->_right);
	}
	Node* _root = nullptr;//根
};

4，二叉搜索树的key和key/value使用场景

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进⾏比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树结构了，可以修改value。

场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输⼊英文，则同时查找到了英文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，⽤当前时间-⼊场时间计算出停车时长，计算出停车费用，缴费后抬杆，⻋辆离场。

场景3：统计⼀篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

上面实现的代码，只是key场景下的，要改成kev/value结构，只需修改参数即可，其他逻辑不变。

代码如下：

template<class K, class V>
	struct BSTNode
	{
		K _key;
		V _value;

		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			, _value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};
	// Key/value
	template<class K, class V>
	class BSTree
	{
		//typedef BSTNode<K> Node;
		using Node = BSTNode<K, V>;
	public:
		// 强制生成构造
		BSTree() = default;

		BSTree(const BSTree& t)
		{
			_root = Copy(t._root);
		}

		BSTree& operator=(BSTree tmp)
		{
			swap(_root, tmp._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				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, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		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->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;

					}
					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;
							}
						}

						delete cur;

					}
					else
					{
						// 左右都不为空
						// 右子树最左节点
						Node* replaceParent = cur;
						Node* replace = cur->_right;
						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replaceParent->_left == replace)
							replaceParent->_left = replace->_right;
						else
							replaceParent->_right = replace->_right;

						delete replace;
					}

					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 << ":" << root->_value << endl;
			_InOrder(root->_right);
		}

		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* newRoot = new Node(root->_key, root->_value);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}
	private:
		Node* _root = nullptr;
	};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-05，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历