【C++】二叉搜索树

在本篇博客中，作者将会讲解普通的二叉搜索树，其目的是为后面的AVLTree和红黑树进行铺垫。

一. 二叉搜索树

那么什么是二叉搜索树呢，二叉树应该大家都能理解，所以顾名思义，二叉搜索树就是一个用来搜索的二叉树，二叉树搜索树也可以叫做一棵二叉排序树，因为它的中序遍历是有序的。

1.性质

二叉搜索树的性质：

1.如果当前结点的左子树不为空，则左子树上的所有结点都小于该当前结点。

2.如果当前结点的右子树不为空，则右子树上的所有结点都大于该当前结点。

3.它的左右子树分别也是二叉搜索树。

即一棵二叉树的中序遍历是有序的就是二叉搜索树，也叫二叉排序树

如下就是一棵二叉搜索树。 

二.二叉搜索树的实现 

那么已经知道了二叉搜索树是什么，也知道了它的性质，那么现在我们来实现一下。

首先，二叉搜索树最主要的接口有下面这几个：

1.插入

2.删除

3.查找

4.修改（注意，不是所有二叉搜索树都能修改的，因为二叉搜索树要严格遵守它的性质，一旦它的性质被破坏，则这棵树就会无意义） 

1.树结点的定义

首先我们来看一下树结点的定义。 

template<class K>
struct Blog_TreeNode
{
	//成员变量
	K _key;
	Blog_TreeNode<K>* _left;
	Blog_TreeNode<K>* _right;

	//成员函数
	Blog_TreeNode(const K& key)//构造函数
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

树结点的定义不是很难，就二叉树常规的定义即可。 

2.类的定义 

我们可以把树结点封装到一个Blog_Tree的类中，在类中实现它的成员函数。 

template<class K>
class Blog_Tree
{
	typedef Blog_TreeNode<K> Node;//typedef一下，这样在类中可以使用Node来代替Blog_TreeNode
public:
    //构造函数
	Blog_Tree()
		:_root(nullptr)
	{}

private:
	Node* _root;//成员变量为一个根节点的指针
};

3.构造函数与析构函数

 对于一个类，有四个比较重要的成员函数：构造函数、析构函数、拷贝构造、赋值=重载。

在这里，拷贝构造和赋值=重载先不做讲解，先把构造函数和析构函数进行讲解。

①构造函数

对于二叉搜索树的构造函数来说非常简单，直接把_root给nullptr即可。

	//构造函数
	Blog_Tree()
		:_root(nullptr)
	{}

②析构函数 

对于析构函数来说，我们可以使用后序遍历来完成。 

	//析构函数
	~Blog_Tree()
	{
		destory(_root);
	}

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

		destory(root->_left);
		destory(root->_right);
		delete root;
	}

 4.插入结点 

二叉搜索树插入结点的过程如下：

1.如果树为空，则直接将新结点给_root根结点。

2.如果树不为空，则将新结点与当前结点进行比较，如果新结点大于当前结点，则当前结点向右走，否则向左走，如果相等，则不插入。

如下图所示。 

接下来我们来编写代码来实现这个过程。 

	//插入结点
	bool insert(const K& data)
	{
		//如果树为空，则直接将新结点给到_root
		if (_root == nullptr)
			_root = new Node(data);

		//如果树不为空，这开始找空位，将新结点插入
		Node* cur = _root;
		Node* cur_parent = nullptr;//这里要提前保留cur的parent，因为后面插入时要用到
		while (cur != nullptr)
		{
			if (data > cur->_key)//如果要插入的数据大于cur，则cur往右走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_right;
			}
			else if (data < cur->_key)//如果要插入的数据小于cur，则cur往左走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_left;
			}
			else//如果相等，说明树中已有，则不插入，返回失败
			{
				return false;
			}
		}

		//找到空位后，将新结点进行插入
		Node* newnode = new Node(data);
		if (cur_parent->_key > newnode->_key)
			cur_parent->_left = newnode;
		else
			cur_parent->_right = newnode;

		return true;
	}

5.删除结点

删除结点是所有操作里面比较难的，但是不要怕，我们来分析一下。 

删除结点，有四种情况：

1.要删除的结点没有左子树和右子树。

2.要删除的结点没有左子树，有右子树。

3.要删除的结点有左子树，没有右子树。

4.要删除的结点有左子树和右子树。

我们基于这四种情况分析一下。 

①要删除的结点没有左子树和右子树 

对于这种情况的处理，非常简单。

我们只需要将该结点删除，让它的parent指向空即可。如下图所示。 

注意！！！在进行删除操作时，要注意一种情况

1.被删除的结点是根结点 

②要删除的结点没有左子树，有右子树 

对于这种情况，也还好，直接将要删除结点的parent指向被删除结点的右孩子即可，如下图所示。 

这里也一样，要判断被删除的cur是否时根结点。 

③要删除的结点有左子树，没有右子树

 这种情况与第二种一样，只不过相反了而已。这里就不多解释。

④ 要删除的结点有左子树和右子树

对于这种情况，我们的解决方法是，去找被删除结点（cur）的右子树的最小结点（即被删除结点的右子树的最左结点）（cur_right_min），后将cur_right_min赋值给cur，这样我们就可以将删除cur转换完删除cur_right_min。如下图所示。

此时删除cur变为删除cur_right_min，那么这个时候删除cur_right_min，也就是第一种情况，或者第二种情况。 

注意！！！这里也可能会有特殊情况，例如，下面这种情况。 

所以最后要进行一个判断。

删除代码如下： 

	//删除结点
	bool erase(const K& data)
	{
		if (_root == nullptr)
			return false;

		//先找到要删除的结点
		Node* cur = _root;
		Node* cur_parent = nullptr;
		while (cur != nullptr)
		{
			//先找到要删除的结点
			if (data > cur->_key)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->_key)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else//找到了cur要删除的结点
			{
				//判断是那种删除情况
				if (cur->_left == nullptr && cur->_right == nullptr)//第一种情况
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = nullptr;
					}
					else
					{
						if (cur_parent->_left == cur)//这里要判断cur时cur_parent左还是右
						{
							cur_parent->_left = nullptr;
						}
						else
						{
							cur_parent->_right = nullptr;
						}
					}
					delete cur;
				}
				else if (cur->_left == nullptr && cur->_right != nullptr)//第二种情况
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = cur->_right;
					}
					else
					{
						if (cur_parent->_left == cur)//这里要判断cur时cur_parent左还是右
						{
							cur_parent->_left = cur->_right;
						}
						else
						{
							cur_parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_left != nullptr && cur->_right == nullptr)//第三种情况
				{
					if (cur_parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur_parent->_left == cur)//这里要判断cur时cur_parent左还是右
						{
							cur_parent->_left = cur->_left;
						}
						else
						{
							cur_parent->_right = cur->_left;
						}
						delete cur;
					}
				}
				else//第四种情况
				{
					Node* cur_right_min = cur->_right;//cur右子树的最小左结点
					Node* cur_right_min_parent = cur;
					while (cur_right_min->_left != nullptr)//去找cur右子树的最小左结点
					{
						cur_right_min_parent = cur_right_min;
						cur_right_min = cur_right_min->_left;
					}
					cur->_key = cur_right_min->_key;//找到后将其赋值给cur，后转变为删除cur_right_min

					if (cur_right_min_parent->_key > cur_right_min->_key)
					{
						cur_right_min_parent->_left = cur_right_min->_right;
					}
					else
					{
						cur_right_min_parent->_right = cur_right_min->_right;
					}
					delete cur_right_min;
				}
				return true;
			}
		}
		return false;
	}

6.查找结点

接下来我们来实现查找结点的函数，查找的过程与插入的过程类似。

1.要查找的值比cur大，则cur往右走。 

2.要查找的值比cur小，则cur往左走。

3.如果找到，则返回该结点的指针，如果没找到，则返回nullptr

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

三. 二叉搜索树的应用

那么二叉搜索树有什么应用了，由名字可以得知，二叉搜索树主要就是用来搜索的。

二叉搜索树的搜索又分为两种模型：K模型，和KV模型。

K模型 

 什么是K模型，K指的是key的意思，如上面我们实现的二叉搜索树就是一种K模型的搜索树，就是在树的结点中，只存储一个K类型的值，剩下的是两个孩子指针。

template<class K>
struct Blog_TreeNode
{
	//成员变量
	K _key;
	Blog_TreeNode<K>* _left;
	Blog_TreeNode<K>* _right;

	//构造函数
	Blog_TreeNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

K模型的主要用途是：查找这个值在不在。

比如说：学校宿舍的门禁系统，在这个门禁系统里面，就有着一棵二叉搜索树，每个树结点K都是一个string类型，存的是该宿舍学生的名字，那么这棵二叉搜索树里面存着你们宿舍里每个学生的姓名，当有一个人想要进入该宿舍的时候，他需要进行刷卡识别，这个时候，程序就会去该宿舍的二叉搜索树中去进行查找，查查这个人的姓名在不在这个二叉搜索树中，如果在就能进入，不在不能进入。

KV模型 

什么是KV模型，K是key，V是value的意思，在树结点中，不仅仅有一个K类型，还有一个V类型，意思就是说，每一个key都对应的一个value的意思，即<key,value>键值对，但是注意的是，在KV模型中，我们依然是使用K来进行比较来插入。

比如说，用来存储单词，又或者说统计次数。下面我会来演示一下。

在演示之前，我们需要需要把我们的K模型的二叉搜索树改造成KV模型的二叉搜索树。

改造非常简单，在树结点结构体中增加一个V类型的值，后将所有成员函数涉及到的K,V都小改一下，例如，插入中，要多传一个参数。改造完后如下所示。 

template<class K, class V>
struct Blog_TreeNode
{
	//成员变量
	K _key;
    V _val;
	Blog_TreeNode<K>* _left;
	Blog_TreeNode<K>* _right;

	//构造函数
	Blog_TreeNode(const K& key, const V& val)
		:_key(key)
        ,_val(val)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K, class V>
class Blog_Tree
{
	typedef Blog_TreeNode<K, V> Node;
public:
	//构造函数
	Blog_Tree()
		:_root(nullptr)
	{}

	//析构函数
	~Blog_Tree()
	{
		destory(_root);
	}

	//插入结点
	bool insert(const K& key, const V& val)
	{
		//如果树为空，则直接将新结点给到_root
		if (_root == nullptr)
		{
			_root = new Node(key, val);
		}

		//如果树不为空，这开始找空位，将新结点插入
		Node* cur = _root;
		Node* cur_parent = nullptr;//这里要提前保留cur的parent，因为后面插入时要用到
		while (cur != nullptr)
		{
			if (key > cur->_key)//如果要插入的数据大于cur，则cur往右走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_right;
			}
			else if (key < cur->_key)//如果要插入的数据小于cur，则cur往左走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_left;
			}
			else//如果相等，说明树中已有，则不插入，返回失败
			{
				return false;
			}
		}

		//找到空位后，将新结点进行插入
		Node* newnode = new Node(key, val);
		if (cur_parent->_key > newnode->_key)
		{
			cur_parent->_left = newnode;
		}
		else
		{
			cur_parent->_right = newnode;
		}

		return true;
	}

	//删除结点
	bool erase(const K& key)
	{
		if (_root == nullptr)
		{
			return false;
		}

		//先找到要删除的结点
		Node* cur = _root;
		Node* cur_parent = nullptr;
		while (cur != nullptr)
		{
			//先找到要删除的结点
			if (key > cur->_key)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else//找到了cur要删除的结点
			{
				//判断是那种删除情况
				if (cur->_left == nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = nullptr;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = nullptr;
						}
						else
						{
							cur_parent->_right = nullptr;
						}
					}
					delete cur;
				}
				else if (cur->_left == nullptr && cur->_right != nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = cur->_right;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_right;
						}
						else
						{
							cur_parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_left != nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_left;
						}
						else
						{
							cur_parent->_right = cur->_left;
						}
						delete cur;
					}
				}
				else
				{
					Node* cur_right_min = cur->_right;//cur右子树的最小左结点
					Node* cur_right_min_parent = cur;
					while (cur_right_min->_left != nullptr)//去找cur右子树的最小左结点
					{
						cur_right_min_parent = cur_right_min;
						cur_right_min = cur_right_min->_left;
					}
					cur->_key = cur_right_min->_key;//找到后将其赋值给cur，后转变为删除cur_right_min

					if (cur_right_min_parent->_key > cur_right_min->_key)
					{
						cur_right_min_parent->_left = cur_right_min->_right;
					}
					else
					{
						cur_right_min_parent->_right = cur_right_min->_right;
					}
					delete cur_right_min;
				}
				return true;
			}
		}
		return false;
	}

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

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

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

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

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

		destory(root->_left);
		destory(root->_right);
		delete root;
	}
private:
	Node* _root;
};

存储单词

接下来我们来演示一下。

//字典树
void Blog_test1()
{
	Blog_Tree<string, string> root;
	root.insert("树", "tree");
	root.insert("排序", "sort");
	root.insert("水", "water");

	Blog_TreeNode<string, string>* tmp = root.find("排序");
	if (tmp == nullptr)
	{
		cout << "无该单词" << endl;
	}
	else
	{
		cout << tmp->_val << endl;
	}
}

在上面的代码中，我们可以在树中存一个又一个的<中文，英文>键值对，通过这个中文可以找到对应的英文。 

统计次数 

//统计次数
void Blog_test2()
{
	string str[] = { "衣服","鞋子","衣服","裤子","衣服","衣服","裤子","鞋子","帽子","帽子","袜子" };
	Blog_Tree<string, int> root;
	for (auto& e : str)
	{
		Blog_TreeNode<string, int>* tmp = root.find(e);//如果树中没有，则插入，并且val给1
		if (tmp == nullptr)
		{
			root.insert(e, 1);
		}
		else//如果树中有，则val++
		{
			tmp->_val++;
		}
	}
	root.InOrder();
}

当我们要插入时，先判断在二叉搜索树中在不在，如果不在，则进行插入，并把val次数给1，如果存储，则对val进行++。 

四.二叉树搜索树的性能

对于二叉搜索树的性能来说，我们可以看到，它的插入和查找最多进行高度次的查找，例如下面这棵树，如果要进行查找最多查找3次，如果要插入，最多也就4次，所以可以得出二叉搜索树的性能为O（logN），其中N为树中结点的个数。

但是我们的树不一定是我们所想的那么理想的，如果要插入的数据完全有序或者接近有序的时候，二叉树会退化成单支树。如下图所示。 

这个时候二叉搜索树的性能就会退化成O（n），这显然不是我们想要的，所以这个时候又衍生出来的AVLTree和红黑树，这两棵树会在后面的博客中进行讲解。 

五.所以源代码 

所以源代码分为K模型的和KV模型的。 

K模型 

BinarySearchTree.h

#pragma once
#include<iostream>
using namespace std;

template<class K>
struct Blog_TreeNode
{
	//成员变量
	K _key;
	Blog_TreeNode<K>* _left;
	Blog_TreeNode<K>* _right;

	//构造函数
	Blog_TreeNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}

};

template<class K>
class Blog_Tree
{
	typedef Blog_TreeNode<K> Node;
public:
	//构造函数
	Blog_Tree()
		:_root(nullptr)
	{}

	//析构函数
	~Blog_Tree()
	{
		destory(_root);
	}

	//插入结点
	bool insert(const K& data)
	{
		//如果树为空，则直接将新结点给到_root
		if (_root == nullptr)
		{
			_root = new Node(data);
		}

		//如果树不为空，这开始找空位，将新结点插入
		Node* cur = _root;
		Node* cur_parent = nullptr;//这里要提前保留cur的parent，因为后面插入时要用到
		while (cur != nullptr)
		{
			if (data > cur->_key)//如果要插入的数据大于cur，则cur往右走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_right;
			}
			else if (data < cur->_key)//如果要插入的数据小于cur，则cur往左走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_left;
			}
			else//如果相等，说明树中已有，则不插入，返回失败
			{
				return false;
			}
		}

		//找到空位后，将新结点进行插入
		Node* newnode = new Node(data);
		if (cur_parent->_key > newnode->_key)
		{
			cur_parent->_left = newnode;
		}
		else
		{
			cur_parent->_right = newnode;
		}

		return true;
	}

	//删除结点
	bool erase(const K& data)
	{
		if (_root == nullptr)
		{
			return false;
		}

		//先找到要删除的结点
		Node* cur = _root;
		Node* cur_parent = nullptr;
		while (cur != nullptr)
		{
			//先找到要删除的结点
			if (data > cur->_key)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->_key)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else//找到了cur要删除的结点
			{
				//判断是那种删除情况
				if (cur->_left == nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = nullptr;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = nullptr;
						}
						else
						{
							cur_parent->_right = nullptr;
						}
					}
					delete cur;
				}
				else if (cur->_left == nullptr && cur->_right != nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = cur->_right;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_right;
						}
						else
						{
							cur_parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_left != nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_left;
						}
						else
						{
							cur_parent->_right = cur->_left;
						}
						delete cur;
					}
				}
				else
				{
					Node* cur_right_min = cur->_right;//cur右子树的最小左结点
					Node* cur_right_min_parent = cur;
					while (cur_right_min->_left != nullptr)//去找cur右子树的最小左结点
					{
						cur_right_min_parent = cur_right_min;
						cur_right_min = cur_right_min->_left;
					}
					cur->_key = cur_right_min->_key;//找到后将其赋值给cur，后转变为删除cur_right_min

					if (cur_right_min_parent->_key > cur_right_min->_key)
					{
						cur_right_min_parent->_left = cur_right_min->_right;
					}
					else
					{
						cur_right_min_parent->_right = cur_right_min->_right;
					}
					delete cur_right_min;
				}
				return true;
			}
		}
		return false;
	}

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

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

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

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

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

		destory(root->_left);
		destory(root->_right);
		delete root;
	}
private:
	Node* _root;
};

test.c 

#include"BinarySearchTree.h"

//测试插入和删除
void Blog_test1()
{
	Blog_Tree<int> root;
	int arr1[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
	for (auto& e : arr1)
	{
		root.insert(e);
	}
	root.InOrder();

	for (auto& e : arr1)
	{
		root.erase(e);
		root.InOrder();
	}
}

//测试查找
void Blog_test2()
{
	Blog_Tree<int> root;
	int arr1[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
	for (auto& e : arr1)
	{
		root.insert(e);
	}
	Blog_TreeNode<int>* tmp = root.find(20);
	if (tmp != nullptr)
	{
		cout << tmp->_key << endl;
	}
	else
	{
		cout << "不存在给值" << endl;
	}
}

int main()
{
	//Blog_test1();
	Blog_test2();
	return 0;
}

 KV模型

BinarySearchTree.h 

template<class K, class V>
struct Blog_TreeNode
{
	//成员变量
	K _key;
	V _val;
	Blog_TreeNode<K, V>* _left;
	Blog_TreeNode<K, V>* _right;

	//构造函数
	Blog_TreeNode(const K& key, const V& value)
		:_key(key)
		,_val(value)
		,_left(nullptr)
		,_right(nullptr)
	{}

};

template<class K, class V>
class Blog_Tree
{
	typedef Blog_TreeNode<K, V> Node;
public:
	//构造函数
	Blog_Tree()
		:_root(nullptr)
	{}

	//析构函数
	~Blog_Tree()
	{
		destory(_root);
	}

	//插入结点
	bool insert(const K& key, const V& val)
	{
		//如果树为空，则直接将新结点给到_root
		if (_root == nullptr)
		{
			_root = new Node(key, val);
		}

		//如果树不为空，这开始找空位，将新结点插入
		Node* cur = _root;
		Node* cur_parent = nullptr;//这里要提前保留cur的parent，因为后面插入时要用到
		while (cur != nullptr)
		{
			if (key > cur->_key)//如果要插入的数据大于cur，则cur往右走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_right;
			}
			else if (key < cur->_key)//如果要插入的数据小于cur，则cur往左走
			{
				cur_parent = cur;//保留cur的parent
				cur = cur->_left;
			}
			else//如果相等，说明树中已有，则不插入，返回失败
			{
				return false;
			}
		}

		//找到空位后，将新结点进行插入
		Node* newnode = new Node(key, val);
		if (cur_parent->_key > newnode->_key)
		{
			cur_parent->_left = newnode;
		}
		else
		{
			cur_parent->_right = newnode;
		}

		return true;
	}

	//删除结点
	bool erase(const K& key)
	{
		if (_root == nullptr)
		{
			return false;
		}

		//先找到要删除的结点
		Node* cur = _root;
		Node* cur_parent = nullptr;
		while (cur != nullptr)
		{
			//先找到要删除的结点
			if (key > cur->_key)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else//找到了cur要删除的结点
			{
				//判断是那种删除情况
				if (cur->_left == nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = nullptr;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = nullptr;
						}
						else
						{
							cur_parent->_right = nullptr;
						}
					}
					delete cur;
				}
				else if (cur->_left == nullptr && cur->_right != nullptr)
				{
					if (cur_parent == nullptr)//如果cur_parent为空，说明删除的cur为_root
					{
						_root = cur->_right;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_right;
						}
						else
						{
							cur_parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_left != nullptr && cur->_right == nullptr)
				{
					if (cur_parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur_parent->_left == cur)
						{
							cur_parent->_left = cur->_left;
						}
						else
						{
							cur_parent->_right = cur->_left;
						}
						delete cur;
					}
				}
				else
				{
					Node* cur_right_min = cur->_right;//cur右子树的最小左结点
					Node* cur_right_min_parent = cur;
					while (cur_right_min->_left != nullptr)//去找cur右子树的最小左结点
					{
						cur_right_min_parent = cur_right_min;
						cur_right_min = cur_right_min->_left;
					}
					cur->_key = cur_right_min->_key;//找到后将其赋值给cur，后转变为删除cur_right_min

					if (cur_right_min_parent->_key > cur_right_min->_key)
					{
						cur_right_min_parent->_left = cur_right_min->_right;
					}
					else
					{
						cur_right_min_parent->_right = cur_right_min->_right;
					}
					delete cur_right_min;
				}
				return true;
			}
		}
		return false;
	}

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

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

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

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

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

		destory(root->_left);
		destory(root->_right);
		delete root;
	}
private:
	Node* _root;
};

 test.c

//字典树
void Blog_test1()
{
	Blog_Tree<string, string> root;
	root.insert("树", "tree");
	root.insert("排序", "sort");
	root.insert("水", "water");

	Blog_TreeNode<string, string>* tmp = root.find("排序");
	if (tmp == nullptr)
	{
		cout << "无该单词" << endl;
	}
	else
	{
		cout << tmp->_val << endl;
	}
}

//统计次数
void Blog_test2()
{
	string str[] = { "衣服","鞋子","衣服","裤子","衣服","衣服","裤子","鞋子","帽子","帽子","袜子" };
	Blog_Tree<string, int> root;
	for (auto& e : str)
	{
		Blog_TreeNode<string, int>* tmp = root.find(e);
		if (tmp == nullptr)
		{
			root.insert(e, 1);
		}
		else
		{
			tmp->_val++;
		}
	}
	root.InOrder();
}

int main()
{
	//Blog_test1();
	Blog_test2();
	return 0;
}