本文将深入探讨二叉搜索树这一重要的数据结构。二叉搜索树不仅是一个功能强大的数据结构，而且在实际应用中展现出了极高的实用性。它以其独特的组织方式，使得查找、插入和删除操作都能在平均对数到线性时间内完成，从而大大提高了数据处理的效率。为了更好地理解二叉搜索树的工作原理，我们使用C++语言实现了一个简单的二叉搜索树。

1. 二叉搜索树的概念

二叉搜索树（Binary Search Tree），也称二叉排序树，是一种特殊的二叉树。二叉搜索树可以为空树。如果不为空树，有以下的性质：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
左子树和右子树也都是二叉搜索树。

2. 二叉搜索树的实现

2.1 二叉树的结构

先自定义一个二叉树结点的类，该类将使用模版。一般来说，有两种类型的二叉搜索树。

K模型：K模型即只有key作为关键码，自定义结点类型中只需要存储Key即可。
KV模型：每一个关键码key，都有与之对应的值Value，即<Key，Value>键值对。

下面的代码是两种模型自定义类的实现，把下面的代码放到BSTree.h文件下。分别封装到key和keyValue的命名空间中。我们先实现K模型的二叉树成员函数。再如法炮制实现第二种模型的成员函数。


#pragma once
#include <iostream>
using namespace std;
 
namespace key
{
	template<class K>
	struct BSTNode
	{
		BSTNode(const K& key = K())
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
 
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;
	};
 
    template<class K>
    class BSTree
    {
	    typedef BSTNode<K> Node;
        //...
    private:
        Node* root;
    }
}
 
namespace keyValue
{
	template<class K, class V>
	struct BSTNode
	{
		BSTNode(const K& key = K(), const V& value = V())
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
 
		K _key;
		V _value;
		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;
	};
 
    template<class K, class V>
    class BSTree
    {
	    typedef BSTNode<K, V> Node;
        //...
    private:
        Node* root;
    }
}

2.2 二叉树查找

二叉搜索树的查找操作比较简单。

函数的返回值是个布尔值。查找成功返回true，失败返回false。
从根开始比较关键码，进行查找。如果关键码比根的大往右边查找，比根的小就往左边查找。
最多会查找这颗二叉树的高度次，如果走到空，说明这个值不存在。


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

2.3 二叉树的插入和中序遍历

int arr[] = {11, 7, 18, 9, 14, 4, 23, 8, 16, 10};

二叉树的插入操作其实步骤根查找类似，插入具体过程如下：

函数的返回值也是布尔值。插入成功返回true，插入失败返回false。
如果树为空，直接使用new创建新结点，赋值给root指针。
如果树不为空，使用while循环查找新结点的位置，如果找到某个节点存储的值，与插入的值相同，就不需要插入，返回false。此外，还要新定义一个二叉树结点类值，此值用来存储当前结点的父亲结点。因为需要判断新增结点是他的父亲结点左节点还是右节点。


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

二叉搜索树可以通过中序遍历得到有序的数据。在类中，定义一个中序遍历的子函数，再传入这棵树的根，进行遍历打印即可。


class BSTree
{
    //...
public:
    //...
    
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
 
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
 
private:
	Node* _root = nullptr;
};

我们写一个测试函数，测试一下插入函数。


#include "BSTree.h"
 
void Test1()
{
	int arr[] = { 11, 7, 18, 9, 14, 4, 23, 8, 16, 10 };
	key::BSTree<int> tree;
 
	for (auto& e : arr)
	{
		tree.Insert(e);
	}
	tree.InOrder();
 
	tree.Insert(2);
	tree.Insert(13);
	tree.InOrder();
}

运行结果如下：

2.4 二叉树的删除

二叉树的删除操作就有些麻烦。需要分几种情况：

待删除结点没有孩子结点。
待删除结点有一个孩子结点。
待删除结点有左右孩子结点。

待删除结点没有孩子结点，可以直接释放该节点，使其父亲结点指向空即可。

待删除结点只有一个孩子结点。如下图，14结点有一个右孩子，左孩子为空。先释放14结点，再将其父亲结点的左指针指向16结点即可。如果待删除结点有一个左孩子，操作也是类似。

不过这个有极端情况，如下面的第二张图，如果要删除的是根节点，并且根节点只有左孩子或者右孩子。此时，因为根结点没有父亲结点，所以直接释放根结点，让root指针指向他的孩子结点。

待删除结点有两个孩子结点的情况，就比较麻烦。如下图，思路是找到可以替换的结点，待删除结点的key值替换成该节点的key值，然后再释放这个替换结点，处理结点之间的连接关系。

第一步需要查找待删除结点，如果没有找到，返回false。找到待删除结点，进行删除操作。
待删除结点的左子树中的最右结点，是左子树中最大的结点，待删除结点的右子树中的最左结点是右子树中最小的结点。我们使用右子树中最左结点来替换待删除结点。
我们先定义一个rightMin结点指针变量，用来找右子树中最小的结点，定义一个rightMinP来记录rightMin指向结点的父亲结点。
其中rightMin一开始指向待删除结点的右孩子。rightMinP需要指向待删除节点，看第二张图片，如果右子树的最小结点就是待删除结点的右孩子，rightMInP不指向待删除节点，而是指向空，那么我们使用rightMinP这个空指针进行操作会有问题。


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//删除操作
		{    
			// 0-1孩子
			if (cur->_left == nullptr)
			{
				if (parent == nullptr)//删除根节点的情况
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}
				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent == nullptr)//删除根节点的情况
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}
				delete cur;
				return true;
			}
			else
			{
				//两个孩子的情况
				// 右子树的最小节点作为替代节点
				Node* rightMinP = cur;//不可为空，特殊情况会访问空指针
				Node* rightMin = cur->_right;
 
				while (rightMin->_left)
				{
					rightMinP = rightMin;
					rightMin = rightMin->_left;
				}
 
				cur->_key = rightMin->_key;
                
                //需要判断右子树最小节点是父亲结点的左孩子还是右孩子
				if (rightMinP->_left == rightMin)
					rightMinP->_left = rightMin->_right;
				else
					rightMinP->_right = rightMin->_right;
 
				delete rightMin;
				return true;
			}
		}
	}
	return false;
}

我们写一个测试函数，测试一些删除函数的功能：


void Test2()
{
	int arr[] = { 11, 7, 18, 9, 14, 4, 23, 8, 16, 10 };
	key::BSTree<int> tree;
 
	for (auto& e : arr)
	{
		tree.Insert(e);
	}
	tree.InOrder();
 
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("第%-2d次:", i + 1);
		tree.Erase(arr[i]);
		tree.InOrder();
	}
}

运行结果如下：

3. 二叉搜索树的应用

3.1 KV模型实现

上文有提到二叉搜索树有两种模型，其中在现实生活中比较常用的是KV模型。每个关键码key，都有对应的的值Value，即<Key，Value>键值对。

下面是KV模型的代码实现：


namespace keyValue
{
	template<class K, class V>
	struct BSTNode
	{
		BSTNode(const K& key = K(), const V& value = V())
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
 
		K _key;
		V _value;
		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;
	};
 
	template<class K, class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;
 
	public:
		BSTree() = default;
 
		BSTree(const BSTree<K, V>& t)
		{
			_root = Copy(t._root);
		}
 
		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}
 
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
			}
 
			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
				{
					// 0-1孩子
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_right;
							else
								parent->_right = cur->_right;
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}
						delete cur;
						return true;
					}
					else
					{
						// 两个孩子的情况
						// 右子树的最小节点作为替代节点
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
 
						while (rightMin->_left)
						{
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
 
						cur->_key = rightMin->_key;
						cur->_value = rightMin->_value;
 
						if (rightMinP->_left == rightMin)
							rightMinP->_left = rightMin->_right;
						else
							rightMinP->_right = rightMin->_right;
 
						delete rightMin;
						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 << " ";
			_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);
		}
 
    private:
		Node* _root = nullptr;
	};
};

3.2 应用

二叉搜索树KV模型的应用有许多

最经典的就是双语词典，英汉词典中，每个英文都有对应的中文，构成<word, chinese>键值对。
中国公民每个人都有对象的身份证号码，即<中国人，身份证号码>键值对。
还可以用来统计词语出现的次数，词语和其出现的次数就构成<word，count>键值对。


void TestBsTree3()
{
	keyValue::BSTree<string, string> dict;
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("apple", "苹果");
	dict.Insert("sort", "排序");
	dict.Insert("love", "爱");
 
	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << "->" << ret->_value << endl;
		}
		else
		{
			cout << "重新输入" << endl;
		}
	}
}

运行结果如下：

这是统计词语出现次数


void TestBSTree4()
{
	// 统计物品出现的次数
	string arr[] = { "书本", "笔", "书本", "笔", "书本", "书本", "笔", "书本", "橡皮", "书本", "橡皮" };
	keyValue::BSTree<string, int> countTree;
 
	for (const auto& str : arr)
	{
		// 先查找物品在不在搜索树中
		// 1、不在，说明物品第一次出现，则插入<物品, 1>
		// 2、在，则查找到的节点中水果对应的次数++
 
		auto ret = countTree.Find(str);
		if (ret == NULL)
			countTree.Insert(str, 1);
		else
			ret->_value++;
 
	}
	countTree.InOrder();
}

运行结果如下：

4. 二叉搜索树分析

二叉搜索树的插入和删除操作，都需要先进行查找。查找操作一般最多查找这颗树的高度次，如果二叉搜索树是一个满二叉树或者完全二叉树，效率很高。可当二叉树退化成下图中右边这颗二叉树，基本上像链表的形态，那么查找的速度比原来慢了很多。

最好的情况，二叉搜索树是接近一颗满二叉树，查找的时间复杂度是O(logN)。
最坏的情况，二叉搜索树退化成只有单链，像链表的形态，查找的时间复杂度是O(N)。

因此，在二叉搜索树的基础上，又出现了平衡二叉搜索树，如AVL树和红黑树，会调整二叉树成为接近满二叉树的形态。

总结

通过本文的阐述，相信你应该对二叉搜索树的基本概念、特性以及操作方法已经有了一定的了解。不过想要掌握这个数据结构，还需要亲自上手编写一个二叉搜索树的代码。通过编码实践，才能更深刻体会到内部的工作机制。

创作不易，希望这篇文章能给你带来启发和帮助，如果喜欢这篇文章，请留下你的三连，你的支持的我最大的动力！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/882400