数据结构高阶–二叉搜索树（原理+实现）

二叉搜索树

概念

二叉搜索树又称为二叉排序树，因为这棵树的中序遍历是有序的。二叉搜索树总结起来有以下几个性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值
• 它的左右子树都是二叉搜索树
• 这棵树中没有重复的元素

举个例子：

二叉搜索树的实现

基本框架

template <class K,class V> struct  BST_Node { 	BST_Node<K,V>* left; 	BST_Node<K,V>* right; 	K key; 	V value; 	//构造函数 	BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value) 	{} }; template <class K,class V> class BST_Tree { 	typedef BST_Node<K,V> Node; public: private: 	Node* root = nullptr; }; 

要实现的接口

bool Insert(const K& key,const V& value);//二叉搜索树的插入 void InOrder();//打印功能，采用中序遍历（递归） Node* Find(const K& key);//二叉搜索树的查找 bool Erase(const K& key);//二叉搜索树的删除 

二叉搜索树的插入

插入分为下面几个步骤：

• 先判断树是否为空，为空就让要插入的这个节点作为根节点，然后结束
• 确定要插入节点的位置
• 用一个cur记录当前节点，parent记录父节点
• 要插入节点的值如果比当前节点的值小，cur就往左走，如果比当前节点的值大，就往右子树走，如果等于就返回false，表面这棵树中有这个数据，不需要插入

//二叉搜索树的插入 	bool Insert(const K& key,const V& value) 	{ 		//没有节点的时候就是根节点 		if (root == nullptr) 		{ 			root = new Node(key,value); 			return true; 		} 		//用一个父节点记录cur的上一个节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			parent = cur; 			//小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 				return false; 		} 		cur = new Node(key,value); 		//判断应该插在父节点的左边还是右边 		if (cur->key < parent->key) 		{ 			parent->left = cur; 		} 		else 		{ 			parent->right = cur; 		} 		return true; 	} 

打印二叉搜索树（中序遍历）

//中序遍历（递归） 	void InOrder() 	{ 		_InOrder(root); 		cout << endl; 	} 	void _InOrder(Node* root) 	{ 		if (root == NULL) 		{ 			return; 		} 		else 		{ 			_InOrder(root->left); 			cout << root->key << ":" << root->value << endl; 			_InOrder(root->right); 		} 	} 

二叉搜索树的查找

查找的步骤如下：（和插入的步骤有些类似）

• 如果查找值key比当前节点的值小，就往左子树走
• 如果查找值key比当前节点的值大，就往右子树走
• 如果查找值key和当前节点的值相等，就返回当前节点的指针

//二叉搜索树的查找 	Node* Find(const K& key) 	{ 		if (root == nullptr) 		{ 			return nullptr; 		} 		Node* cur = root;//遍历结点 		while (cur) 		{ 			//小于往左走 			if (cur->key > key) 			{ 				cur = cur->left; 			} 			else if (cur->key < key) 			{ 				cur = cur->right; 			} 			else 			{ 				return cur; 			} 		} 		return nullptr; 	} 

二叉搜索树的删除（难）

分四种情况：我们一个一个来讨论

以下面这颗树为例：

情景一：

情景二：

还要分析一种特殊的情况，就是此时2没有父亲节点，也就是自己为根时，看下面如何操作

情景三：

该节点如果为根节点，就让自己的右孩子变成根节点

情景四：

总结： 一共有四种情况，但是情况1可以归为情况3，因为它也是左为空，所以整体处理下来是三种情况

//二叉搜索树的删除 bool Erase(const K& key) { 	//树为空，删除失败 	if (root == nullptr) 	{ 		return false; 	} 	//parent始终是cur的父亲节点 	//cur就是要找的删除的当前节点 	Node* parent = nullptr; 	Node* cur = root; 	while (cur) 	{ 		//小于往左边走 		if (key < cur->key) 		{ 			parent = cur; 			cur = cur->left; 		} 		else if (key > cur->key) 		{ 			parent = cur; 			cur = cur->right; 		} 		else 		{ 			// 找到了，开始删除 			// 1.左右子树都为空，直接删除，可以归类为左为空 			// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左   			// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除  			//当前情况是情景三，删除的节点它的左为空，右未知 			if (cur->left == nullptr) 			{ 				// 要删除节点为根节点时，直接把右子树的根节点赋值给——root 				// 根节点的话会导致parent为nullptr 				if (root == cur) 				{ 					root = root->right; 				} 				else 				{ 					//左为空，父亲指向我的右 					//判断cur在父亲的左还是右 					if (parent->left == cur) 					{ 						parent->left = cur->right; 					} 					else 					{ 						parent->right = cur->right; 					} 				} 				delete cur; 				cur = nullptr; 			} 			//当前情况是情景二，删除节点它的右为空，左未知 			else if (cur->right == nullptr) 			{ 				if (root ==cur ) 				{ 					root = root->left; 				} 				else 				{ 					//右为空，父亲指向我的左 					//判断cur在父亲的左还是右 					if (parent->left == cur) 					{ 						parent->left = cur->left; 					} 					else 					{ 						parent->right = cur->left; 					} 				} 				delete cur; 				cur = nullptr; 			} 			//只剩下情景四 			else 			{ 				//找右子树中最小的节点，当前cur就是要删除的节点 				Node* rightMinParent = cur; 				Node* rightMin = cur->right;//去右子树找最小的节点 				while (rightMin->left) 				{ 					rightMinParent = rightMin; 					rightMin = rightMin->left; 				} 				//替代删除 				cur->key = rightMin->key; 				//转化成了情景三，左孩子为空 				if (rightMinParent->left == rightMin) 					rightMinParent->left = rightMin->right; 				else 					rightMinParent->right = rightMin->right;  				delete rightMin; 				rightMin = nullptr; 			} 			return true; 		} 	} 	return false; } 

完整代码以及测试

#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 template <class K > struct  BST_Node { 	BST_Node<K>* left; 	BST_Node<K>* right; 	K key; 	//构造函数 	BST_Node(const K& key):left(nullptr),right(nullptr),key(key) 	{} }; template <class K> class BST_Tree { 	typedef BST_Node<K> Node; public: 	//二叉搜索树的插入 	bool Insert(const K& key) 	{ 		//没有节点的时候就是根节点 		if (root == nullptr) 		{ 			root = new Node(key); 			return true; 		} 		//用一个父节点记录cur的上一个节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			parent = cur; 			//小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 				return false; 		} 		cur = new Node(key); 		//判断应该插在父节点的左边还是右边 		if (cur->key < parent->key) 		{ 			parent->left = cur; 		} 		else 		{ 			parent->right = cur; 		} 		return true; 	} 	//中序遍历（递归） 	void InOrder() 	{ 		_InOrder(root); 		cout << endl; 	} 	void _InOrder(Node* root) 	{ 		if (root == NULL) 		{ 			return; 		} 		else 		{ 			_InOrder(root->left); 			cout << root->key <<" "; 			_InOrder(root->right); 		} 	} 	//二叉搜索树的查找 	Node* Find(const K& key) 	{ 		if (root == nullptr) 		{ 			return nullptr; 		} 		Node* cur = root;//遍历结点 		while (cur) 		{ 			//小于往左走 			if (cur->key > key) 			{ 				cur = cur->left; 			} 			else if (cur->key < key) 			{ 				cur = cur->right; 			} 			else 			{ 				return cur; 			} 		} 		return nullptr; 	} 	//二叉搜索树的删除 	bool Erase(const K& key) 	{ 		//树为空，删除失败 		if (root == nullptr) 		{ 			return false; 		} 		//parent始终是cur的父亲节点 		//cur就是要找的删除的当前节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			//小于往左边走 			if (key < cur->key) 			{ 				parent = cur; 				cur = cur->left; 			} 			else if (key > cur->key) 			{ 				parent = cur; 				cur = cur->right; 			} 			else 			{ 				// 找到了，开始删除 				// 1.左右子树都为空，直接删除，可以归类为左为空 				// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左   				// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除  				//当前情况是情景三，删除的节点它的左为空，右未知 				if (cur->left == nullptr) 				{ 					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root 					// 根节点的话会导致parent为nullptr 					if (root == cur) 					{ 						root = root->right; 					} 					else 					{ 						//左为空，父亲指向我的右 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->right; 						} 						else 						{ 							parent->right = cur->right; 						}  					} 					delete cur; 					cur = nullptr;  				} 				//当前情况是情景二，删除节点它的右为空，左未知 				else if (cur->right == nullptr) 				{ 					if (root ==cur ) 					{ 						root = root->left; 					} 					else 					{ 						//右为空，父亲指向我的左 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->left; 						} 						else 						{ 							parent->right = cur->left; 						} 					} 					delete cur; 					cur = nullptr; 				} 				//只剩下情景四 				else 				{ 					//找右子树中最小的节点，当前cur就是要删除的节点 					Node* rightMinParent = cur; 					Node* rightMin = cur->right;//去右子树找最小的节点 					while (rightMin->left) 					{ 						rightMinParent = rightMin; 						rightMin = rightMin->left; 					} 					//替代删除 					cur->key = rightMin->key; 					//转化成了情景三，左孩子为空 					if (rightMinParent->left == rightMin) 						rightMinParent->left = rightMin->right; 					else 						rightMinParent->right = rightMin->right;  					delete rightMin; 					rightMin = nullptr; 				} 				return true; 			} 		} 		return false; 	} private: 	Node* root = nullptr; }; void TestBSTree() { 	BST_Tree<int> bt; 	int arr[] = { 5,3,4,1,7,8,2,6,0,9 }; 	for (auto e : arr) 	{ 		cout << "插入 " << e << " 后："; 		bt.Insert(e); 		bt.InOrder(); 	}  	cout << "------------------------------" << endl; 	for (auto e : arr) 	{ 		cout << "删除 " << e << " 后："; 		bt.Erase(e); 		bt.InOrder(); 	}  } int main() { 	TestBSTree(); 	system("pause"); 	return EXIT_SUCCESS; } 

二叉搜索树的应用

二叉搜索树有两种模型：

• K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
• KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value。（我们平时查找单词就是通过中文找英文，或者通过英文找中文）

上面的测试代码是KV模型改成了K模型，接下来我们来看看KV模型的作用

#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 template <class K,class V> struct  BST_Node { 	BST_Node<K,V>* left; 	BST_Node<K,V>* right; 	K key; 	V value; 	//构造函数 	BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value) 	{} }; template <class K,class V> class BST_Tree { 	typedef BST_Node<K,V> Node; public: 	//二叉搜索树的插入 	bool Insert(const K& key,const V& value) 	{ 		//没有节点的时候就是根节点 		if (root == nullptr) 		{ 			root = new Node(key,value); 			return true; 		} 		//用一个父节点记录cur的上一个节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			parent = cur; 			//小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 				return false; 		} 		cur = new Node(key,value); 		//判断应该插在父节点的左边还是右边 		if (cur->key < parent->key) 		{ 			parent->left = cur; 		} 		else 		{ 			parent->right = cur; 		} 		return true; 	} 	//中序遍历（递归） 	void InOrder() 	{ 		_InOrder(root); 		cout << endl; 	} 	void _InOrder(Node* root) 	{ 		if (root == NULL) 		{ 			return; 		} 		else 		{ 			_InOrder(root->left); 			cout << root->key << ":" << root->value << endl; 			_InOrder(root->right); 		} 	} 	//二叉搜索树的查找 	Node* Find(const K& key) 	{ 		if (root == nullptr) 		{ 			return nullptr; 		} 		Node* cur = root;//遍历结点 		while (cur) 		{ 			//小于往左走 			if (cur->key > key) 			{ 				cur = cur->left; 			} 			else if (cur->key < key) 			{ 				cur = cur->right; 			} 			else 			{ 				return cur; 			} 		} 		return nullptr; 	} 	//二叉搜索树的删除 	bool Erase(const K& key) 	{ 		//树为空，删除失败 		if (root == nullptr) 		{ 			return false; 		} 		//parent始终是cur的父亲节点 		//cur就是要找的删除的当前节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			//小于往左边走 			if (key < cur->key) 			{ 				parent = cur; 				cur = cur->left; 			} 			else if (key > cur->key) 			{ 				parent = cur; 				cur = cur->right; 			} 			else 			{ 				// 找到了，开始删除 				// 1.左右子树都为空，直接删除，可以归类为左为空 				// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左   				// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除  				//当前情况是情景三，删除的节点它的左为空，右未知 				if (cur->left == nullptr) 				{ 					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root 					// 根节点的话会导致parent为nullptr 					if (root == cur) 					{ 						root = root->right; 					} 					else 					{ 						//左为空，父亲指向我的右 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->right; 						} 						else 						{ 							parent->right = cur->right; 						}  					} 					delete cur; 					cur = nullptr;  				} 				//当前情况是情景二，删除节点它的右为空，左未知 				else if (cur->right == nullptr) 				{ 					if (root ==cur ) 					{ 						root = root->left; 					} 					else 					{ 						//右为空，父亲指向我的左 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->left; 						} 						else 						{ 							parent->right = cur->left; 						} 					} 					delete cur; 					cur = nullptr; 				} 				//只剩下情景四 				else 				{ 					//找右子树中最小的节点，当前cur就是要删除的节点 					Node* rightMinParent = cur; 					Node* rightMin = cur->right;//去右子树找最小的节点 					while (rightMin->left) 					{ 						rightMinParent = rightMin; 						rightMin = rightMin->left; 					} 					//替代删除 					cur->key = rightMin->key; 					//转化成了情景三，左孩子为空 					if (rightMinParent->left == rightMin) 						rightMinParent->left = rightMin->right; 					else 						rightMinParent->right = rightMin->right;  					delete rightMin; 					rightMin = nullptr; 				} 				return true; 			} 		} 		return false; 	} private: 	Node* root = nullptr; }; int main() { 	system("pause"); 	return EXIT_SUCCESS; } 

实例1

英汉字典

void TestBSTree_KV1() { 	// 创建一个简易的字典 	BST_Tree<string, string> dict;  	dict.Insert("苹果", "apple"); 	dict.Insert("香蕉", "banana"); 	dict.Insert("橘子", "orange"); 	dict.Insert("葡萄", "grape"); 	dict.Insert("apple", "苹果"); 	dict.Insert("banana", "香蕉"); 	dict.Insert("orange", "橘子"); 	dict.Insert("grape", "葡萄");  	string str; 	while (cin >> str) 	{ 		BST_Node<string, string>* ret = dict.Find(str); 		if (ret) 		{ 			cout << ret->value << endl; 		} 		else 		{ 			cout << "本字典无此词" << endl; 		} 	} } 

实例2

统计树

void TestBSTree_KV2() { 	// 统计水果个数 	BST_Tree<string, int> countTree;  	string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };  	for (auto e : strArr) 	{ 		BST_Node<string, int>* ret = countTree.Find(e); 		if (ret == nullptr) 		{ 			// 第一次插入 			countTree.Insert(e, 1); 		} 		else 		{ 			ret->value++; 		} 	}  	countTree.InOrder(); }