【c++】二叉搜索树

mosheng

发布于 2026-01-14 18:41:27

250

文章被收录于专栏：c++c++

hello~ 很高兴见到大家! 这次带来的是C++中关于二叉搜索树这部分的一些知识点,如果对你有所帮助的话,可否留下你宝贵的三连呢? 个人主页: 默|笙

一、二叉搜索树的概念

二叉搜索树又称二叉排序树，因为中序遍历这棵树得到的是一组排好序的数（前提是这棵树没有重复的值）。这棵树要么是一棵空树，要么满足以下性质：

若它的左子树不为空，那么它左子树上的节点的值都小于等于根节点的值。
若它的右子树不为空，那么它右子树上的节点的值都大于等于根节点的值。
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值具体要看使用场景定义。

二、二叉搜索树的性能分析

二叉树的增删查找效率取决与被查找的值在这棵树上面的深度，深度越大，查找效率越低。

最优情况下，二叉搜索树接近完全二叉树的时候，其高度为logN。
最差情况下，二叉搜索树退化接近单只树的时候，其高度为N。
综合而言，二叉搜索树增删查改时间复杂度为：O(N)。

关于二分查找（logN）的弊端：

需要存储在支持下标随机访问（vector、deque）的结构中，并且有序。
插入和删除效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般都要挪动其他数据。

三、插入

当二叉搜索树为一棵空树的时候，直接增加新节点，并赋值给root。
不为空树时，将插入值与根节点值进行比较，若小于根节点则往左走，大于根节点则往右走，再与它新的根节点值进行比较，直到找到空的位置，插入新节点。
如果支持插入相等的值，这个相等的值可以往左走，也可以往右走，找到空位置，插入新节点。（要注意的是要保持逻辑一致性，不能一会儿往左走，一会儿又往右走）

1.实现

这里我们实现的是没有重复数据的二叉搜索树。

template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* left;
	BSTNode<K>* right;

	BSTNode(const K& key)
		:_key(key)
		,left(nullptr)
		,right(nullptr)
	{ }
};

template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	//插入
	bool Insert(const K& key)
	{
		if (!_root)
		{
			_root = new Node(key);
		}
		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;
			}
		}
		if (parent->_key > key)
		{
			parent->left = new Node(key);
		}
		else
		{
			parent->right = new Node(key);
		}
	}
	//调用中序遍历需要传递实参_root
	//我们在外面是无法拿到_root的，所以需要经过一些处理，将中序遍历函数放到private中
	//再写一个public里的调用中序遍历的函数便可，这样能够拿到_root传递给函数。
	////中序遍历
	//void _InOrder(Node* _root)
	//{
	//	if (!_root)
	//	{
	//		return;
	//	}
	//	_InOrder(_root->left);
	//	cout << _root->_key << " ";
	//	_InOrder(_root->right);
	//}
	
	//调用函数
	void InOrder()
	{
		_InOrder(_root);
	}
	
private:

	//中序遍历
	void _InOrder(Node* _root)
	{
		if (!_root)
		{
			return;
		}
		_InOrder(_root->left);
		cout << _root->_key << " ";
		_InOrder(_root->right);
	}
	Node* _root = nullptr;
};

先用struct定义二叉搜索树节点BSTNode类，然后用class定义二叉搜索树类BSTree（拥有私有成员_root，这是根节点），并在里面实现对二叉搜索树的增删查改工作。
由于我们给了_root一个缺省值，默认生成的构造函数就已经够用，这里不再写出。
对于Insert（插入）函数，函数逻辑：若没有根节点，则插入根节点，否则进入while语句对key进行查找，没有查找到即cur为nullptr（找到了key应该插入的位置），parent为cur父节点的时候，key将根据大小插入parent的左边或右边，返回true表示插入成功；查到了就代表这个搜索二叉树里面已经存在这个数了，返回false表示插入失败。
这里需要定义一个parent指针，用来完成对key的插入操作，因为cur为nullptr，这时候无法找到它的父节点。
关于InOrder（中序遍历）函数，中序遍历函数逻辑就先省略掉了。这里将_InOrder放进private域里，然后在public域里添加一个调用函数的原因是：倘若仅只有一个_InOrder函数放在public域里，我们想要调用这个函数就必须将二叉搜索树的根传过去，但是这个根它是私有成员，拿不到。所以我们需要在类里面拿到_root并把它传递给_InOrder函数–>调用函数。

bool Insert(const K& key)
{
	return _Insert(_root, key);
}

bool _Insert(Node*& _root, const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	if (key > _root->_key)
	{
		_Insert(_root->right, key);
	}
	else if (key < _root->_key)
	{
		_Insert(_root->left, key);
	}
	else
	{
		return false;
	}
}

也可以通过递归来实现插入函数，关键在于Node*& 是引用，这让我们可以通过在最后一层递归里赋值给_root直接修改其父节点的指向。

四、查找

查找就比较简单了，跟插入寻找key值的逻辑差不多，这里不多做解释。

//查找
bool Find(const K& key)
{
	Node* cur = _root;

	while (cur)
	{
		if (key > cur->_key)
		{
			cur = cur->right;
		}
		else if (key < cur->_key)
		{
			cur = cur->left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

五、删除

首先需要查找需要删除的元素是否存在于二叉搜索树当中是，如果不存在，则需要返回false，表示删除失败。
若查找成功，删除节点则需要考虑节点的情况，一个节点拥有四种情况：

删除节点左右子树都为空。
删除节点左子树为空，右子树不为空。
删除节点右子树为空，左子树不为空。
删除节点左右子树均不为空。
对于第一种，需要把要删除节点的父节点指向空，然后直接删除节点，该情况可以包含在第二种或第三种情况里。

对于第二种，需要把要删除节点的父节点指向它不为空的右子树，然后删除节点。

对于第三种，需要把要删除节点的父节点指向它不为空的左子树，然后删除节点。
对于第四种，最麻烦的情况，我们需要找到要删除节点的左子树里的最大值或者是右子树里面的最小值与它要删除节点的值进行交换。如果找的是左子树里的最大值，那么最大值节点的右子树一定为空，需要将它的父节点指向它的左子树（左子树不一定为空），如果找的是右子树里的最小值，那么最小值节点的左子树一定为空，需要将它的父节点指向它的右子树。最后删除节点。即1. 找到它的左子树最大值或右子树最小值，2. 与要删除节点的值进行交换，3. 将原左子树最大值的父节点指向它的左子树或将原右子树最小值的父节点指向它的右子树，4. 删除原左子树最大值节点或原右子树最小值节点。

删除一定要保证不破坏原来的二叉搜索树的结构。

//删除
bool Erase(const K& key)
{
	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
		{
			//如果左子树为空,右子树为空或不为空
			if (cur->left == nullptr)
			{
				if (cur != _root)
				{
					//若要删除节点是其父节点的左孩子
					if (parent->left == cur)
					{
						parent->left = cur->right;
					}
					//要删除节点是其父节点的右孩子
					else
					{
						parent->right = cur->right;
					}
				}
				else
				{
					_root = _root->right;
				}
				delete cur;
			}
			//如果左子树不为空，右子树为空
			else if (cur->right == nullptr)
			{
				if (cur != _root)
				{
					if (parent->left == cur)
					{
						parent->left = cur->left;
					}
					else
					{
						parent->right = cur->left;
					}
					delete cur;
				}
				else
				{
					_root = _root->left;
				}
				delete cur;
			}
			//两个子树都不为空
			else
			{
				//找到右子树的最小值节点
				Node* RightMin = cur->right;
				Node* RightMinParent = cur;
				while (RightMin->left)
				{
					RightMinParent = RightMin;//存储一下最小值节点的父节点
					RightMin = RightMin->left;
				}
				swap(cur->_key, RightMin->_key);//交换两个节点的值
				RightMinParent->left = RightMin->right;
				delete RightMin;
			}
			return true;
		}
	}
	return false;
}

总体可以分为三种情况：左子树为空，右子树为空且左子树不为空与左右子树皆不为空。
要注意前两种情况下要考虑要删除节点是其父节点的左孩子还是右孩子，还要考虑如果要删除的是根节点的情况下，需要改变根节点。
第三种还需要考虑删除的是根节点的情况，如果是根节点若根节点的右孩子是没有左子树的话那么是进不去循环的，RightMinParent不会被更新，在之后的指针接引用里会出现问题，所以RightMinParent初始化时不要赋值为nullpter，而是cur。

六、二叉搜索树key和key/value使用场景

1. key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，因为修改key会破坏搜索树的结构。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车主的业主的车牌号录入后台系统，车辆进入是扫描车牌在不在系统中，在则允许通行，否则无法进入。
场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中不再则标红提示。

key二叉搜索树代码：

	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* left;
		BSTNode<K>* right;

		BSTNode(const K& key)
			:_key(key)
			, left(nullptr)
			, right(nullptr)
		{
		}
	};

	template<class K>
	class BSTree
	{
		typedef BSTNode<K> Node;
	public:
		//插入
		bool Insert(const K& key)
		{
			if (!_root)
			{
				_root = new Node(key);
			}
			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;
				}
			}
			if (parent->_key > key)
			{
				parent->left = new Node(key);
			}
			else
			{
				parent->right = new Node(key);
			}
		}
		/*bool Insert(const K& key)
		{
			return _Insert(_root, key);
		}

		bool _Insert(Node*& _root, const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			if (key > _root->_key)
			{
				_Insert(_root->right, key);
			}
			else if (key < _root->_key)
			{
				_Insert(_root->left, key);
			}
			else
			{
				return false;
			}
		}*/
		//调用中序遍历需要传递实参_root
		//我们在外面是无法拿到_root的，所以需要经过一些处理，将中序遍历函数放到private中
		//再写一个public里的调用中序遍历的函数便可，这样能够拿到_root传递给函数。
		////中序遍历
		//void _InOrder(Node* _root)
		//{
		//	if (!_root)
		//	{
		//		return;
		//	}
		//	_InOrder(_root->left);
		//	cout << _root->_key << " ";
		//	_InOrder(_root->right);
		//}

		//调用函数
		void InOrder()
		{
			_InOrder(_root);
		}

		//查找
		bool Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (key > cur->_key)
				{
					cur = cur->right;
				}
				else if (key < cur->_key)
				{
					cur = cur->left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

		//删除
		bool Erase(const K& key)
		{
			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
				{
					//如果左子树为空,右子树为空或不为空
					if (cur->left == nullptr)
					{
						if (cur != _root)
						{
							//若要删除节点是其父节点的左孩子
							if (parent->left == cur)
							{
								parent->left = cur->right;
							}
							//要删除节点是其父节点的右孩子
							else
							{
								parent->right = cur->right;
							}
						}
						else
						{
							_root = _root->right;
						}
						delete cur;
					}
					//如果左子树不为空，右子树为空
					else if (cur->right == nullptr)
					{
						if (cur != _root)
						{
							if (parent->left == cur)
							{
								parent->left = cur->left;
							}
							else
							{
								parent->right = cur->left;
							}
							delete cur;
						}
						else
						{
							_root = _root->left;
						}
						delete cur;
					}
					//两个子树都不为空
					else
					{
						//找到右子树的最小值节点
						Node* RightMin = cur->right;
						Node* RightMinParent = cur;
						while (RightMin->left)
						{
							RightMinParent = RightMin;//存储一下最小值节点的父节点
							RightMin = RightMin->left;
						}
						swap(cur->_key, RightMin->_key);//交换两个节点的值
						RightMinParent->left = RightMin->right;
						delete RightMin;
					}
					return true;
				}
			}
			return false;
		}

	private:

		//中序遍历
		void _InOrder(Node* _root)
		{
			if (!_root)
			{
				return;
			}
			_InOrder(_root->left);
			cout << _root->_key << " ";
			_InOrder(_root->right);
		}
		Node* _root = nullptr;
	};
}

2. key/value搜索场景

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

场景1：简单中英互译词典，树的结构中（节点）存储key（英文）和value（中文），搜索时输入英文，则同时查到了英文对应的中文。
场景2：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现。节点存储key单词与value次数，单词若存在，则++单词对应的次数。

以下是key/value二叉搜索树代码：

:
	//插入
	bool Insert(const K& key, const V& value)
	{
		if (!_root)
		{
			_root = new Node(key, value);
		}
		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;
			}
		}
		if (parent->_key > key)
		{
			parent->left = new Node(key, value);
		}
		else
		{
			parent->right = new Node(key, value);
		}
	}

	//调用函数
	void InOrder()
	{
		_InOrder(_root);
	}

	//查找
	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->right;
			}
			else if (key < cur->_key)
			{
				cur = cur->left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	//删除
	bool Erase(const K& key)
	{
		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
			{
				//如果左子树为空,右子树为空或不为空
				if (cur->left == nullptr)
				{
					if (cur != _root)
					{
						//若要删除节点是其父节点的左孩子
						if (parent->left == cur)
						{
							parent->left = cur->right;
						}
						//要删除节点是其父节点的右孩子
						else
						{
							parent->right = cur->right;
						}
					}
					else
					{
						_root = _root->right;
					}
					delete cur;
				}
				//如果左子树不为空，右子树为空
				else if (cur->right == nullptr)
				{
					if (cur != _root)
					{
						if (parent->left == cur)
						{
							parent->left = cur->left;
						}
						else
						{
							parent->right = cur->left;
						}
						delete cur;
					}
					else
					{
						_root = _root->left;
					}
					delete cur;
				}
				//两个子树都不为空
				else
				{
					//找到右子树的最小值节点
					Node* RightMin = cur->right;
					Node* RightMinParent = cur;
					while (RightMin->left)
					{
						RightMinParent = RightMin;//存储一下最小值节点的父节点
						RightMin = RightMin->left;
					}
					swap(cur->_key, RightMin->_key);//交换两个节点的值
					RightMinParent->left = RightMin->right;
					delete RightMin;
				}
				return true;
			}
		}
		return false;
	}

private:

	//中序遍历
	void _InOrder(Node* _root)
	{
		if (!_root)
		{
			return;
		}
		_InOrder(_root->left);
		cout << _root->_key << " " <<  _root->_value << " ";
		_InOrder(_root->right);
	}
	Node* _root = nullptr;
};