33.C++二叉树进阶2（二叉搜索树两种模型及其应用）

⭐上篇文章：32.C++二叉树进阶1（二叉搜索树）-CSDN博客

⭐本篇代码：c++学习/18.二叉树进阶-二叉搜索树 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

⭐标⭐是比较重要的部分

        在上篇文章中，实现了一个简单的二叉搜索树，包括插入数据，删除数据，查找数据，搜索二叉树的中序遍历。

        上篇文章中的二叉搜索树代码，其实就是key模型。

key 模型。每一个节点都只存储一个值。

key - value模型。每一个节点除了存储key以外，还存储一个value值

在key-value模型中，通过对应的key来获取它的value。key值一般用于插入，查找，删除，遍历的时候的比较。

目录

一. 二叉搜索树的key模型

二. 二叉搜索树的key - value 模型 

2.1 二叉搜索树节点

2.2 二叉搜索树类

2.3 查找

2.4 插入 

2.5 删除 

2.6 中序遍历 

 三. 二叉搜索树的应用与效率分析  

3.1 查找单词

3.2 统计次数

3.3 二叉搜索树的效率分析以及如何改进 

一. 二叉搜索树的key模型

内容可以见上篇文章：32.C++二叉树进阶1（二叉搜索树）-CSDN博客

代码如下：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

//模板的声明和定义要放在一起
template <class K>
struct BSTreeNode	//Binary Search Tree Node
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	//需要定义构造函数
	BSTreeNode(const K& k)
		:_left(nullptr)
		,_right(nullptr)
		,_key(k)
	{}
};

template <class K>
class BSTree	//Binary Search Tree
{
	typedef BSTreeNode<K> Node;
private:
	Node* _root = nullptr;

public:
	//插入
	bool Insert(const K& key)//使用bool做返回值的目的是二叉搜索树是不允许有冗余的!
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;//成功插入
		}

		Node* cur = _root;//局部变量
		Node* parent = cur;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
				
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
				
			}
			else
			{
				return false;//有一个一摸一样的值，返回false
			}
				
		}
		cur = new Node(key);//还没有将这个新的节点和其父亲链接起来
		if (parent->_key > key)//当前值比父亲小，在其左边
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}

	//查找
	bool find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		//出循环还没返回true，说明该树没有所查找的数据，返回false
		return false;
	}

	//删除(最难的)
	bool Erase(const K& key)
	{
		//1.没有孩子直接删除即可

		//2.有一个孩子的让其父亲指向其孩子，然后将其删除即可

		//3.有两个孩子的最麻烦，需要使用替换删除法
		//需要找到一个节点来替换这个节点！
		//可以找到左子树的最大节点，右子树的最小节点都能够替代

		
		Node* cur = _root;
		Node* parent = cur;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//找到了,可以删除
				if (cur->_left == nullptr)//错误，留坑1
				{
					//左为空
					if (cur == _root)//当要删除的节点为根节点时，需要特判
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;

				}
				else if (cur->_right == nullptr)//错误，留坑1
				{
					//右为空
					//同理，当删除节点为根节点时，需要特判
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
				}
				else
				{
					//找到左子树最大，或者右子树最小来替换我，然后删除
					//这里采用右子树的最小进行删除
					
					Node* rightMin = cur->_right;
					Node* rightMinParent = cur;
					//一直向左寻找即可
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					//然后将rightMin删除即可
					//要注意如果，rightMin没有左孩子（即righMin为要删除节点的右孩子）
					//此时只要让当前节点指向rightMin的右孩子即可
					if (rightMin == cur->_right)//错误，留坑2
					{
						cur->_right = rightMin->_right;
					}
					else
					{
						rightMinParent->_left = rightMin->_right;
					}
				
					delete rightMin;
				}
				return true;
			}
		}
		//找不到，返回false
		return false;
	}

	//修改？，key模型搜索树是不能修改的！
	//key-value模型搜索树可以修改value
	//！！key不可修改


	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//前序遍历
	void PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}

	void PostOrder()
	{
		_PostOrder(_root);
		cout << endl;
	}
private:
	void _PreOrder(Node* root)
	{
		if (root == nullptr)
			return;
		cout << root->_key << " ";
		_PreOrder(root->_left);
		_PreOrder(root->_right);
	}	
	
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

	void _PostOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout << root->_key << " ";
	}
};

key模型中，我们不能修改任意的一个节点的值。

二. 二叉搜索树的key - value 模型 

        key-value模型中，我们可以修改对应的value值。

2.1 二叉搜索树节点

        对于节点来说，需要再模板中增加一个V值，然后再结构体中新增一个_value

//模板的声明和定义要放在一起
template <class K, class V>
struct BSTreeNode	//Binary Search Tree Node
{
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;
	K _key;
	V _value;

	//需要定义构造函数
	BSTreeNode(const K& k, const V& v)
		:_left(nullptr)
		, _right(nullptr)
		, _key(k)
		,_value(v)
	{}
};

2.2 二叉搜索树类

         同理要更新模板和节点

template <class K,class V>
class BSTree	//Binary Search Tree
{
	typedef BSTreeNode<K, V> Node;
private:
	Node* _root = nullptr;
};

2.3 查找

        对于查找来说，不再是返回true/false 而是返回这个节点的指针，若二叉搜索树中没有该节点返回nullptr即可

	//查找
	Node* find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return Node;
			}
		}
		return nullptr;
	}

2.4 插入 

        这里的插入，是在函数内部构造节点，所有要新增一个value参数。如果参数的已经创建好的节点，则不需要改变。

	//插入
	bool Insert(const K& key, const V& value)//使用bool做返回值的目的是二叉搜索树是不允许有冗余的!
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;//成功插入
		}

		Node* cur = _root;//局部变量
		Node* parent = cur;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;

			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;

			}
			else
			{
				return false;//有一个一摸一样的值，返回false
			}

		}
		cur = new Node(key, value);//还没有将这个新的节点和其父亲链接起来
		if (parent->_key > key)//当前值比父亲小，在其左边
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}

2.5 删除 

        由于我们不需要构造节点，所以这里的删除和key模型是一样的。

	bool Erase(const K& key)
	{
		//1.没有孩子直接删除即可

		//2.有一个孩子的让其父亲指向其孩子，然后将其删除即可

		//3.有两个孩子的最麻烦，需要使用替换删除法
		//需要找到一个节点来替换这个节点！
		//可以找到左子树的最大节点，右子树的最小节点都能够替代


		Node* cur = _root;
		Node* parent = cur;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//找到了,可以删除
				if (cur->_left == nullptr)//错误，留坑1
				{
					//左为空
					if (cur == _root)//当要删除的节点为根节点时，需要特判
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;

				}
				else if (cur->_right == nullptr)//错误，留坑1
				{
					//右为空
					//同理，当删除节点为根节点时，需要特判
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
				}
				else
				{
					//找到左子树最大，或者右子树最小来替换我，然后删除
					//这里采用右子树的最小进行删除

					Node* rightMin = cur->_right;
					Node* rightMinParent = cur;
					//一直向左寻找即可
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					//然后将rightMin删除即可
					//要注意如果，rightMin没有左孩子（即righMin为要删除节点的右孩子）
					//此时只要让当前节点指向rightMin的右孩子即可
					if (rightMin == cur->_right)//错误，留坑2
					{
						cur->_right = rightMin->_right;
					}
					else
					{
						rightMinParent->_left = rightMin->_right;
					}

					delete rightMin;
				}
				return true;
			}
		}
		//找不到，返回false
		return false;
	}

2.6 中序遍历 

        中序遍历除了打印key值，还需要打印对应的value

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}

 三. 二叉搜索树的应用与效率分析  

3.1 查找单词

#define _CRT_SECURE_NO_WARNINGS 1
#include "test.h"
#include <iostream>
#include <vector>
using namespace std;

//1.查找单词
void test1()
{
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("print", "打印");
	dict.Insert("sort", "排序");
	dict.Insert("apple", "苹果");
	dict.Insert("world", "世界");
	dict.Insert("tree", "树");

	while (1)
	{
		cout << "请输入你需要查找的单词:";
		string word; cin >> word;
		BSTreeNode<string, string>* node = dict.find(word);
		if (node)
		{
			cout << "中文为:" << node->_value << endl;
		}
		else
			cout << "单词错误，或者该单词不在该字典中" << endl;
	}

}

int main()
{
	test1();
	return 0;
}

运行结果如下：

可以看到，成功的查找到了加载的单词

3.2 统计次数

        如果将key值定义为需要统计的类型，value值定义为int。这样就能够统计次数

//统计次数
void test2()
{
	string s = "1234asdjh@#$#@%ns$#^%**&(*__+daigo`123~+_)(*&^%$#@!{}|: < > ? , / .;p[]\ vughw4895WEFyWERuoei328750`4u3;[. / .za`~!@#$";
	BSTree<char, int> counttree;
	for (int i = 0; i < s.size(); i++)
	{
		BSTreeNode<char, int>* node = counttree.find(s[i]);
		if (node == nullptr)
			counttree.Insert(s[i], 1);
		else
			node->_value++;
	}
	counttree.InOrder();
}

int main()
{
	//test1();
	test2();
	return 0;
}

运行结果如下：

3.3 二叉搜索树的效率分析以及如何改进 

        根据二叉树的性质，如果一颗二叉树为满二叉树，那么其搜索效率为O(logN)，因为此时根据大小判断可以直接去除一半的节点。

        但是在极端的情况下，二叉搜索树可能会退化为链表(比如插入的数据是有序的时候)，此时效率为O(N)。

想要解决这个问题需要使用平衡二叉搜索树，常见的平衡二叉搜索树有：

1 AVL树

2 红黑树