C++入门小馆： 二叉搜索树

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉 领略算法真谛

目录

二叉搜索树的特性：

搜索二叉树的实现

Insert

Find：

Erase

析构函数：

拷贝函数和赋值运算符重载

key_value

二叉搜索树的特性：

之前我们学习过了二叉树，但实现二叉树是没有意义的，我们针对二叉树进行一定的限制就出现了二叉搜索树：它的每个节点满足根节点上的左子树上的节点小于它的父节点，右子树上的节点大于根节点。

这就是一棵二叉搜索树：

二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值，我们今天就实现不能插入相同的值吧！

那我们的二叉搜索树有什么特性呢？

我们对这一棵树进行中序遍历我们发现打印出来就成了升序。因为这种特性我们也叫二叉搜索树为二叉排序树，因为这种特性我们进行查找某一个元素也很高效。

我们要进行搜索操作时，我们需要的时间复杂度最差的情况是h，那⼆叉搜索树增删查改时间复杂度是什么呢？有人说是log N，这是理想的情况下，如果我们的树是这样的呢？

这样显然的时间复杂度为O(N)。

搜索二叉树的实现

我们得定义树节点，和二叉树两种结构：

#pragma once
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _right;
	BSTreeNode<K>* _left;
	K _key;
	BSTreeNode(const K& key)
		: _right(nullptr)
		, _left(nullptr)
		, _key(key)
	{ }
};
template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;
private:
	Node* _root = nullptr;
};

我们先来实现一下插入操作：

Insert

插入操作就很简单，如果插入的值小于该节点，就向它的左子树走，否则就向右子树走，如果要走的子树为空就插入在这个位置，我们实现的Insert返回类型应该是bool类型来判断是否插入成功，我们由于要找到上一个节点的位置才能插入，所以可以多定义一个指针。

//只能插入不同的Key节点
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 (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

实现了插入，我们来实现一下中序遍历来打印一下吧：

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

但如果我们在外部调用这个函数时我们访问不了私有变量_root，我们该怎么实现呢？函数体类实现返回_root函数，这样还是太麻烦了，不如这样实现：

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

我们可以随便实现一下查找，思路是一样的

Find：

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

接下来就来实现比较复制的删除操作了

如果我们删除1节点或者13节点就很简单，让他们的根节点指向空就可以了。

现在如果删除有一个节点的比如先删6，我们怎么处理呢？我们需要将6的父节点指向6的孩子节点，14节点也是一样的思路，但我们得知道它是父节点的左孩子还是右孩子，它唯一的孩子是左孩子还是右孩子，这就得分类讨论了，其实第一种情况可以合并在这一起。

这里还有一种特殊情况当我们要删除的节点只有一个孩子并且它是根节点

此时我们只需要将根节点变成唯一的孩子处。简单来实现一下：

	bool Erase(const K& key)
	{
		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
			{
				//删除操作
				//左孩子为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = _root->_right;
						delete cur;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
						delete cur;
					}
				}
				//右孩子为空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = _root->_left;
						delete cur;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
						delete cur;
					}
				}
				//有两个孩子
				else
				{
					//....
				}    
                return true;
			}
		}
		//找不到
		return false;
	}

到了最麻烦的情况了如果有两个孩子：

此时我们就不能直接删除那么简单了，我们需要将该节点替换之后再删，我们可以找右孩子中最小的替换，或者找左孩子中最大的替换后依然还是一棵平衡二叉树。

比如我们以删除3号节点为例找右孩子中最小的：

我们就可以来实现一下咯：

Erase

bool Erase(const K& key)
{
	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
		{
			//删除操作
			//左孩子为空
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = _root->_right;
					delete cur;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
					delete cur;
				}
			}
			//右孩子为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = _root->_left;
					delete cur;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
					delete cur;
				}
			}
			//有两个孩子
			else
			{
				Node* pMinRight = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					pMinRight = minRight;
					minRight = minRight->_left;
				}
				cur->_key = minRight->_key;
				if (pMinRight->_left == minRight)
				{
					pMinRight->_left = minRight->_right;
				}
				else
				{
					pMinRight->_right = minRight->_right;
				}
				delete minRight;
			}
			return true;
		}
	}
	//找不到
	return false;
}

 剩下的操作就是很简单的了。

析构函数：

我们先来实现一下Destory，因为析构函数不能调用参数，而我们析构要知道_root还是和之前的中序遍历一样的思路：

~BSTree()
{
	Destory(_root);
	_root = nullptr;
}
//销毁
void Destory(Node* root)
{
	if (root == nullptr) return;
	Destory(_root->_left);
	Destory(_root->_right);
	delete _root;
}

接着实现拷贝函数和赋值运算符重载

拷贝函数和赋值运算符重载

BSTree() = default;

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
	swap(t._root, _root);
	return *this;
}
Node* Copy(Node* root)
{
	if (root == nullptr) return nullptr;
	Node* copy = new Node(root->_key);
	copy->_left = Copy(root->_left);
	copy->_right = Copy(root->_right);
	return copy;
}

注意我们实现了拷贝函数，就不会实现默认构造，所以我们得实现一下默认构造函数。

完整代码：

#pragma once
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _right;
	BSTreeNode<K>* _left;
	K _key;
	BSTreeNode(const K& key)
		: _right(nullptr)
		, _left(nullptr)
		, _key(key)
	{ }
};
template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;
	BSTree() = default;

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(t._root, _root);
		return *this;
	}
	~BSTree()
	{
		Destory(_root);
		_root = nullptr;
	}

	//只能插入不同的Key节点
	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 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 (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	bool Erase(const K& key)
	{
		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
			{
				//删除操作
				//左孩子为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = _root->_right;
						delete cur;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
						delete cur;
					}
				}
				//右孩子为空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = _root->_left;
						delete cur;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
						delete cur;
					}
				}
				//有两个孩子
				else
				{
					Node* pMinRight = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						pMinRight = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key;
					if (pMinRight->_left == minRight)
					{
						pMinRight->_left = minRight->_right;
					}
					else
					{
						pMinRight->_right = minRight->_right;
					}
					delete minRight;
				}
				return true;
			}
		}
		//找不到
		return false;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	//销毁
	void Destory(Node* root)
    {
    	if (root == nullptr) return;
    	Destory(root->_left);
    	Destory(root->_right);
    	delete root;
    }
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr) return nullptr;
		Node* copy = new Node(root->_key);
		copy->_left = Copy(root->_left);
		copy->_right = Copy(root->_right);
		return copy;
	}
private:
	//缺省值初始化
	Node* _root = nullptr;
};

 我们也可以实现，key_value类型的搜索二叉树：

key_value

#pragma once
namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _right;
		BSTreeNode<K, V>* _left;
		K _key;
		V _value;
		BSTreeNode(const K& key, const V& value)
			: _right(nullptr)
			, _left(nullptr)
			, _key(key)
			, _value(value)
		{}
	};
	template<class K, class V>
	class BSTree
	{
	public:
		typedef BSTreeNode<K, V> Node;
		BSTree() = default;

		BSTree(const BSTree<K, V>& t)
		{
			_root = Copy(t._root);
		}
		BSTree<K, V>& operator=(BSTree<K, V> t)
		{
			swap(t._root, _root);
			return *this;
		}
		~BSTree()
		{
			Destory(_root);
			_root = nullptr;
		}

		//只能插入不同的Key节点
		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 Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				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, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}
		bool Erase(const K& key)
		{
			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
				{
					//删除操作
					//左孩子为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = _root->_right;
							delete cur;
						}
						else
						{
							if (parent->_right == cur)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
							delete cur;
						}
					}
					//右孩子为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = _root->_left;
							delete cur;
						}
						else
						{
							if (parent->_right == cur)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
							delete cur;
						}
					}
					//有两个孩子
					else
					{
						Node* pMinRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pMinRight = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key;
						if (pMinRight->_left == minRight)
						{
							pMinRight->_left = minRight->_right;
						}
						else
						{
							pMinRight->_right = minRight->_right;
						}
						delete minRight;
					}
					return true;
				}
			}
			//找不到
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		//销毁
		void Destory(Node* root)
		{
			if (root == nullptr) return;
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
		//中序遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr) return nullptr;
			Node* copy = new Node(root->_key, root->_value);
			copy->_left = Copy(root->_left);
			copy->_right = Copy(root->_right);
			return copy;
		}
	private:
		//缺省值初始化
		Node* _root = nullptr;
	};

}