【数据结构--C++】二叉搜索树：一听就会一写就废？这份带源码的避坑指南请收好！

小陈又菜

发布于 2025-12-24 11:06:03

1220

到今天，我们已经基本熟悉了C++的基础语法，之前我们学习的数据结构基础是使用C语言来描述的。那么今天对于进阶的数据结构我们使用C++语言来进行描述。本篇我们将学习二叉树的进阶版，二叉搜索树。

1. 二叉树搜索树

1.1. 二叉搜索树的概念

二叉搜索树又称二叉排序树（BST，Binary Search Tree），它或者是一个空树，或者满足下面的条件：

左子树不为空，且左子树上的所有节点值都小于根节点值
右子树不为空，且右子树上的所有节点值都小于根节点值
左右子树均为二叉搜索树

我们举两个例子：

1. 如图这并不是一个二叉搜索树，因为红圈地方，5 是 7 的右子树，并没有满足右子树值大于根节点。

2. 这是一个二叉搜索树，满足左子树上所有节点值小于根节点，右子树值大于根节点的性质。

1.2. 二叉搜索树的操作

二叉树的实现在文章附录（模拟实现，包含全部结构）

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

递归查找：

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

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

1.2.2. 二叉搜索树的插入

如果树为空，直接将值赋给根节点
如果树不为空，通过二叉树的性质找到插入的位置
然后判断是放在左节点还是右节点

下面举一个例子，对下面这个二叉搜索树插入12：

那么此时我们还应该思考一下有没有插入不成功的情况，因为二叉搜索树的性质就是左子树节点都小于根节点，右子树节点都大于根节点，所以如果插入值已经存在，那么这个插入操作肯定是无法成功的。

我们来试着写一下插入的非递归版本：

//插入
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;
}

insert的递归写法一下有点卡壳，之后我在补上。

1.2.3. 二叉搜索树的删除

我们先来讨论一下可能遇到的情况：

要删除的节点没有孩子节点
要删除的节点没有左孩子节点
要删除的节点没有右孩子节点
要删除的节点有左孩子节点、也有右孩子节点

在进行概括的话就是三种情况：

要删除的节点没有左孩子节点
要删除的节点没有右孩子节点
要删除的节点有左孩子、右孩子

我们来分情况看一下具体的实现细节：

该节点没有左孩子：

我们这里同样是使用parent来记录父节点，cur作为查询指针，当找到10的位置时，可能会有下面几种情况：

该节点就是根节点，将右孩子节点指针赋给根节点指针即可
cur = parent -> right （图中删除10），让parent -> right = cur -> right
cur = parent -> left（图中删除4），让parent -> left = cur ->right
最后delete掉cur即可

				if (cur->_left == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}

上面先展示了核心功能的部分代码，后面将会完整地展示。

该节点没有右孩子：

要删除节点14，逻辑和上面删除的节点没有左孩子类似：

				else if (cur->_right == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}

该节点有左孩子和右孩子：

这里我们先以删除3为例做一个讲解：

我们先通过二叉搜索树性质找到了3的位置（这里我们定义MinPartNode=cur，MinNode）
然后我们应该交换3，和3的右子树的最小值（可以将MinNode指向3的右孩子，然后一直往左走，知道空为止，该节点就是右子树最小的）
交换了之后，删除3就变成了删除右子树最小的节点
最后我们判断这个MinNode是MinPartNode的左孩子还是右孩子，如果是左孩子（这里的删除3），那么只需要MinPartNode -> left = MinNode -> right；如果是右孩子（就是这里删除10的情况），那么只需要MinPartNode -> right = MinNode -> right

	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
			{
				//找到了
				// 1. 该节点没有左孩子
				// 2. 该节点没有右孩子
				if (cur->_left == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					//有两个节点，替换
					Node* MinParNode = cur;
					Node* MinNode = cur->_right;
					while (MinNode->_left)
					{
						MinParNode = MinNode;
						MinNode = MinNode->_left;
					}
					swap(cur->_key, MinNode->_key);
					//if (MinNode->_right != nullptr)//自己写的  错误的
					if(MinParNode->_left == MinNode)//老师写的
					{
						MinParNode->_left = MinNode->_right;
					}
					else
					{
						MinParNode->_right = MinNode->_right;
					}
					delete MinNode;
				}
 
				return true;
			}
		}
		return false;
	}

2. 二叉搜索树的应用

2.1. K模型

K模型顾名思义就是只有key作为关键码，结构中只需要储存key即可（关键码是指搜索中需要的值），我们上述讲到的就是K模型。

2.2. K-V模型

K-V模型的实现在附录，K-V模型就是说每一个key都对应一个value，也就是结构中储存的是<Key，Value>键值对。

3. 二叉搜索树的性能分析

在二叉搜索树的操作中，插入和删除都需要进行查找，所以查找的效率就决定了二叉搜索树的操作效率。

对于一棵二叉树来说，假设每一个元素的查找概率相同，那么平均查找效率应该与二叉搜索树的深度有关，也就是说二叉搜索树越深，次数就会越多。

但是我们还应该注意到一点，二叉搜索树虽然有着右子树永远大于根节点，左子树永远小于根节点这一性质，但是二叉搜索树并不是唯一的，它与关键码的插入顺序是由关系的：

当插入顺序最优时，将会生成完成二叉树（或者接近完全二叉树），其平均比较次数为：log_2 N
当插入顺序比较差时，二叉搜索树就会退化成为单支树（或者接近单支树），其平均比较次数为：N

优化：

如果因为不良的插入顺序，导致退化成为了单支树的话，就会丧失二叉搜索树的性能，所以通过优化二叉搜索数的插入规则，我们就有了平衡二叉搜索树（AVL树），以及红黑树（RB树）。

附录

1.二叉搜索树的模拟实现（K模型）

//二叉搜索树结点的结构
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;//结点重命名为Node
private:
	//递归思想析构
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;
		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}
	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* copynode = new Node(root->_key);
		copynode->_left = CopyTree(root->_left);
		copynode->_right = CopyTree(root->_right);
 
		return copynode;
	}
public:
	//强制编译器自己生成构造
	//C++
	BSTree() = default;
 
	BSTree(const BSTree<K>& t)
	{
		_root = CopyTree(t._root);
	}
 
	//t1 = t2
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}
 
	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}
	//插入
	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 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* 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
			{
				//找到了
				// 1. 该节点没有左孩子
				// 2. 该节点没有右孩子
				if (cur->_left == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					//判断跟
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							//cur 比 parent大
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					//有两个节点，替换
					Node* MinParNode = cur;
					Node* MinNode = cur->_right;
					while (MinNode->_left)
					{
						MinParNode = MinNode;
						MinNode = MinNode->_left;
					}
					swap(cur->_key, MinNode->_key);
					//if (MinNode->_right != nullptr)//自己写的  错误的
					if(MinParNode->_left == MinNode)//老师写的
					{
						MinParNode->_left = MinNode->_right;
					}
					else
					{
						MinParNode->_right = MinNode->_right;
					}
					delete MinNode;
				}
 
				return true;
			}
		}
		return false;
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
	}
 
	//////////////////////////////////////////////////
	//递归方法
	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->_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* MinNode = root->_right;
				while (MinNode->_left)
				{
					MinNode = MinNode->_left;
				}
				swap(root->_key, MinNode->_key);
				
				return _EraseR(root->_right, 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;
		}
	}
	//这里之间  InsertR好理解 EraseR暂时不好理解
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
 
		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return true;
		}
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
 
private:
	Node* _root = nullptr;
};

2.KV模型模拟实现

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;
 
	const 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:
 
	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;
			// 删除
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
 
				swap(root->_key, minRight->_key);
 
				return _EraseR(root->_right, 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 == nullptr)
			return;
 
		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

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

原始发表：2025-10-14，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索