二叉搜索树

本专栏内容为：数据结构学习专栏， 通过本专栏的深入学习，你可以了解并掌握数据结构。

💓博主csdn个人主页：小小unicorn
?专栏分类：数据结构
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

例如下面这颗树：

由于二叉搜索树中，每个结点左子树上所有结点的值都小于该结点的值，右子树上所有结点的值都大于该结点的值，因此对二叉搜索树进行中序遍历后，得到的是升序序列。

二叉搜索树的实现

知道了什么是二叉树，我们就可以自己实现一下二叉搜索树。

节点类

要实现二叉树，首先我们需要一个节点类：

1.节点类要包含三个成员：节点值，左指针，右指针
2、节点类中只需实现一个构造函数即可，用于构造指定节点值的节点。

//节点类：
//摸版参数用K(key 关键字)
template<class K>
struct BSTreeNode
{
	K _key;//节点值
	 BSTreeNode<K>* _left;//左指针
	 BSTreeNode<K>* _right;//右指针

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

各函数接口总览

//二叉搜索树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//构造函数
	BSTree();
	//拷贝构造函数
	BSTree(const BSTree<K>& t);
	//赋值运算符重载函数
	BSTree<K>& operator=(BSTree<K> t);

	//析构函数
	~BSTree();
	//插入函数
	bool Insert(const K& key);
    //递归插入：
    bool InsertR(const K& key);

	//删除函数
	bool Erase(const K& key);
    //递归删除：
    bool EraseR(const K& key);
	//查找函数
	 bool Find(const K& key);
	 //递归查找：
     bool FindR(const K& key);
	//中序遍历
	void InOrder();
private:
   //中序遍历子函数
    void _Inorder(Node* root);
   //递归插入
   bool _InsertR(Node*& root, const K& key);
   //递归删除：
   bool _EraseR(Node*& root, const K& key);
	//递归查找
	bool _FindR(Node* root, const K& key);
	
	Node* _root=nullptr; //指向二叉搜索树的根结点
};

构造函数

构造函数非常简单，构造一个空树即可。
这里给出两种构造的方式：

方式一：

BSTree()
	:_root(nullptr)
{
}

方式二：

//构造函数二：C++11
BSTree() = default;

拷贝构造函数

拷贝构造函数：拷贝一棵和所给二叉搜索树相同的树即可。

//拷贝函数：
Node* Copy(Node* root)
{
	//空树直接返回
	if (root == nullptr)
		return nullptr;
	//拷贝根节点
	Node* newRoot = new Node(root->_key);
	//拷贝左子树
	newRoot->_left = Copy(root->_left);
	//拷贝右子树
	newRoot->_right = Copy(root->_right);
	//返回拷贝的树
	return newRoot;
}
//拷贝构造：
BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

注意： 拷贝构造函数完成的是深拷贝。

赋值运算符重载函数

对于赋值运算符重载函数，下面提供两种实现方法：

传统方法：
先将当前二叉搜索树中的结点释放，然后完成所给二叉搜索树的拷贝即可。

const BSTree<K>& operator=(const BSTree<K>& t)
{
	//防止自己给自己赋值
	if (this != &t)
	{
		//先将当前的二叉搜索树中的节点释放
		Destory(_root);
		//拷贝t对象的二叉搜索树
		_root = Copy(t._root);
	}
	return *this;
}

现代写法：
赋值运算符重载函数的现代写法非常精辟，函数在接收右值时并没有使用引用进行接收，因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换，就相当于完成了赋值操作，而拷贝构造出来的对象t会在该赋值运算符重载函数调用结束时自动析构。

//现代写法：
BSTree<K>& operator=(BSTree<K> t) //编译器接收右值的时候自动调用拷贝构造函数
{
	swap(_root, t._root); //交换这两个对象的二叉搜索树
	return *this; //支持连续赋值
}

注意： 这里传统写法和现代写法完成的都是深拷贝。

析构函数

析构函数完成对象中二叉搜索树结点的释放，注意释放时采用后序释放，当二叉搜索树中的结点被释放完后，将对象当中指向二叉搜索树的指针及时置空即可。

//析构函数
void Destory(Node* root)
{
	if (root == nullptr)
		return;
	//释放左子树
	Destory(root->_left);
	//释放右子树
	Destory(root->_right);
	//释放根节点
	delete root;
	root = nullptr;
}
//析构函数：
~BSTree()
{
	//释放二叉搜索树
	Destory(_root);
}

中序遍历：

为了在实现其他接口的过程中方便随时检查，最好实现一个二叉搜索树的中序遍历接口，当我们对二叉搜索树进行一次操作后，可以调用中序遍历接口对二叉搜索树进行遍历，若二叉搜索树进行操作后的遍历结果仍为升序，则可以初步判断所实现的接口是正确。

//中序遍历的子函数
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left); //遍历左子树
	cout << root->_key << " "; //遍历根结点
	_InOrder(root->_right); //遍历右子树
}
//中序遍历
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

插入函数

根据二叉搜索树的性质，其插入操作非常简单：
1.如果是空树，则直接将插入结点作为二叉搜索树的根结点。
2.如果不是空树，则按照二叉搜索树的性质进行结点的插入。

若不是空树，插入结点的具体操作如下：

1.若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
2.若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
3.若待插入结点的值等于根结点的值，则插入结点失败。

如此进行下去，直到找到与待插入结点的值相同的结点判定为插入失败，或者最终插入到某叶子结点的左右子树当中（即空树当中）。

非递归实现

使用非递归方式实现二叉搜索树的插入函数时，我们需要定义一个parent指针，该指针用于标记待插入结点的父结点。
这样一来，当我们找到待插入结点的插入位置时，才能很好的将待插入结点与其父结点连接起来。

但是需要注意在连接parent和cur时，需要判断应该将cur连接到parent的左边还是右边。

//非递归插入：
bool Insert(const K& key)
{
	//空树
	if (_root == nullptr)
	{
		//new一个节点
		_root = new Node(key);
		//插入成功，返回true
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		parent = cur;
		//插入值比key小，往左走
		if (key < cur->_key)
		{
			//往该节点的左子树走
			cur = cur->_left;
		}
		//插入值比key大，往右走
		else if (key > cur->_key)
		{
			//往该节点的右子树走
			cur = cur->_right;
		}
		//相等
		else
		{
			//插入失败，返回true
			return false;
		}
	}
		//链接：
		//申请一个新节点
		cur = new Node(key);
		//节点值小于父亲节点
		if (key < parent->_key)
		{
			parent->_left = cur;
		}
		//节点值大于父亲节点
		else
		{
			parent->_right = cur;
		}
	return true;
}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.Insert(e);
	}
	bt.InOrder();
	return 0;
}

测试如下：

递归实现

递归实现二叉搜索树的插入操作也是很简单的，但是要特别注意的一点就是，递归插入函数的子函数接收参数root时，必须采用引用接收，因为只有这样我们才能将二叉树当中的各个结点连接起来。

//递归插入：
bool InsertR(const K& key)
{
	return _InsertR(_root, key);
}
//递归插入子函数
bool _InsertR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		//直接申请值为key的节点作为树的根节点
		root = new Node(key);
		//插入成功，返回true;
		return true;
	}

	//key小于跟节点的值
	if (key < root->_key)
	{
		//节点插入到左子树中
		return _InsertR(root->_left,key);
	}
	//key大于根节点的值
	else if (key > root->_key)
	{
		//节点插入到右子树中
		return _InsertR(root->_right, key);
	}
	//key的值等于根节点的值
	else
		return false;
}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	return 0;
}

测试结果如下：

删除函数

二叉搜索树的删除函数是最难实现的，若是在二叉树当中没有找到待删除结点，则直接返回false表示删除失败即可，但若是找到了待删除结点，此时就有以下三种情况：

1.待删除结点的左子树为空（待删除结点的左右子树均为空包含在内）。
2.待删除结点的右子树为空。
3.待删除结点的左右子树均不为空。

下面我们分别对这三种情况进行分析处理：

1.待删除结点的左子树为空

若待删除结点的左子树为空，那么当我们在二叉搜索树当中找到该节点后，只需先让其父节点指向该节点的右孩子节点，然后再将该节点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性。

再删除前还要判断节点在那个位置。也会有三种情况：

第一种：
当删除的节点为根节点，此时的parent为nullptr,首先要更新根节点：

情况二：
当删除节点是其父亲节点的左孩子：

让父亲节点的左指向该节点的右。

情况二：
当删除节点是其父亲节点的右孩子：

让父亲节点的右指向该节点的右。

2.待删除结点的右子树为空

若待删除节点的右子树为空，那么当我们在二叉搜索树当中找到该节点后，只需先让其父节点指向该结点的左孩子节点，然后再将该节点释放便完成了该节点的删除，进行删除操作后仍保持二叉搜索树的特性。

再删除前还要判断节点在那个位置。也会有三种情况：

第一种：
当删除的节点为根节点，此时的parent为nullptr,首先要更新根节点：

情况二：
当删除节点是其父亲节点的左孩子：

让父亲节点的左指向该节点的左。

情况三：
当删除节点是其父亲节点的孩子：

让父亲节点的右指向该节点的左。

3.待删除结点的左右子树均不为空

若待删除结点的左右子树均不为空，那么当我们在二叉搜索树当中找到该结点后，可以使用替换法进行删除。

可以将让待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除（下面都以后者为例），然后将待删除结点的值改为代替其被删除的结点的值即可。而代替待删除结点被删除的结点，必然左右子树当中至少有一个为空树，因此删除该结点的方法与前面说到的情况一和情况二的方法相同。

注意只能是待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除，因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性。

非递归实现

对于二叉搜索树删除函数的实现，在删除左右子树均不为空的结点时有两种不同的思路，因此实现删除函数的方法有以下两种。

方法一：

在遇到待删除结点的左右子树均不为空的情况时，采用的处理方法如下：

1.使用minParent标记待删除结点右子树当中值最小结点的父结点。
2.使用minRight标记待删除结点右子树当中值最小的结点。

当找到待删除结点右子树当中值最小的结点时，先将待删除结点的值改为minRight的值，之后直接判断此时minRight是minParent的左孩子还是右孩子，然后对应让minParent的左指针或是右指针转而指向minRight的右孩子（注意：minRight的左孩子为空），最后将minRight结点进行释放即可。

// 方法一：
//非递归删除：
bool Erase(const K& key)
{
	//标记删除节点的父亲节点
	Node* parent = nullptr;
	//标记删除节点
	Node* cur = _root;
	while (cur)
	{
		//删除节点小于key
		if (key < cur->_key)
		{
			//往该节点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		//删除节点大于key
		else if (key > cur->_key)
		{
			//往该节点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		//找到该节点了准备删除
		else
		{
			//待删除节点的左子树为空：
			if (cur->_left == nullptr)
			{
				//删除节点是根节点，此时的parent为空
				if (cur == _root)
				{
					_root = cur->_right;
				}
				//不是根节点：
				else
				{
					//删除节点是其父节点的左孩子：
					if (cur == parent->_left)
					{
						//父节点的左指针指向待删除节点的右子树
						parent->_left = cur->_right;
					}
					//删除节点是其父节点的右孩子
					else
					{
						//父节点的右指针指向待删除节点的右子树
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}

			//待删除节点的右子树为空：
			else if (cur->_right == nullptr)
			{
				//删除节点是根节点，此时的parent为空
				if (cur == _root)
				{
					_root = cur->_left;
				}
				//不是根节点：
				else
				{
					//删除节点是其父节点的左孩子：
					if (cur == parent->_left)
					{
						//父节点的左指针指向待删除节点的左子树
						parent->_left = cur->_left;
					}
					//删除节点是其父节点的右孩子
					else
					{
						//父节点的右指针指向待删除节点的左子树
						parent->_right = cur->_left;
					}
				}
				//释放删除节点
				delete cur;
				
			}

			//删除节点的左右孩子都不为空：替换法删除
			else
			{
                //替换法删除：
				//左子树的最大节点或者右子树的最小节点
				//我们用右子树的最小节点：

				//记录待删除节点右子树最小节点的父亲节点
				Node* minParent = cur;
				//记录待删除节点右子树最小节点
				Node* minRight = cur->_right;

				//寻找待删除节点右子树最小节点：
				while (minRight->_left)
				{
					//往右走：
					minParent = minRight;
					minRight = minRight->_left;
				}
				//将待删除节点的值改为minRight的值:
				//cur->_key = minRight->_key;
				swap(cur->_key, minRight->_key);

				//隐含条件：minRight的_left为空：
				//MinRight是其父节点的左孩子
				if (minRight == minParent->_left)
					//父亲的左孩子指向minRight的右子树
					minParent->_left = minRight->_right;
				//minRight是其父节点的右孩子
				else
					//父亲的右指针指向minRight的右子树
					minParent->_right = minRight->_right;
				
				delete minRight;
			}
			return true;
		}
	}
//没有找到该节点删除失败：
return false;
}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	bt.Erase(10);
	bt.InOrder();
	bt.Erase(8);
	bt.InOrder();
	return 0;
}

测试结果：

方法二：

方法二在遇到待删除结点的左右子树均不为空的情况时的处理方式与方法一不同，方法二在找到待删除结点右子树当中值最小的结点后，先将minRight的值记录下来，然后再重新调用删除函数删除二叉树当中的minRight，当minRight被删除后再将原待删除结点的值改为minRight的值，这样也完成了左右子树均不为空的结点的删除。

bool Erase(const K& key)
{
	//标记删除节点的父亲节点
	Node* parent = nullptr;
	//标记删除节点
	Node* cur = _root;
	while (cur)
	{
		//删除节点小于key
		if (key < cur->_key)
		{
			//往该节点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		//删除节点大于key
		else if (key > cur->_key)
		{
			//往该节点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		//找到该节点了准备删除
		else
		{
			//待删除节点的左子树为空：
			if (cur->_left == nullptr)
			{
				//删除节点是空节点，此时的parent为空
				if (cur == _root)
				{
					_root = cur->_right;
				}
				//不是空节点：
				else
				{
					//删除节点是其父节点的左孩子：
					if (cur == parent->_left)
					{
						//父节点的左指针指向待删除节点的右子树
						parent->_left = cur->_right;
					}
					//删除节点是其父节点的右孩子
					else
					{
						//父节点的右指针指向待删除节点的右子树
						parent->_right = cur->_right;
					}
				}
				delete cur;

			}

			//待删除节点的右子树为空：
			else if (cur->_right == nullptr)
			{
				//删除节点是空节点，此时的parent为空
				if (cur == _root)
				{
					_root = cur->_left;
				}
				//不是空节点：
				else
				{
					//删除节点是其父节点的左孩子：
					if (cur == parent->_left)
					{
						//父节点的左指针指向待删除节点的左子树
						parent->_left = cur->_left;
					}
					//删除节点是其父节点的右孩子
					else
					{
						//父节点的右指针指向待删除节点的左子树
						parent->_right = cur->_left;
					}
				}
				//释放删除节点
				delete cur;
			}

			//删除节点的左右孩子都不为空：替换法删除
			else
			{
				//替换法删除：
				//左子树的最大节点或者右子树的最小节点
				//我们用右子树的最小节点：

				//记录待删除节点右子树最小节点
				Node* minRight = cur->_right;

				//寻找待删除节点右子树最小节点：
				while (minRight->_left)
				{
					//往右走：
					minRight = minRight->_left;
				}
				//记录minRight节点的值：
				K minKey = minRight->_key;
				//minRight代替待删除节点被删除
				Erase(minKey);
				//将待删除节点的值改为代替其他被删除的节点的值，也就是minRight
				cur->_key = minKey;
			}
			return true;
		}
	}
	//没有找到该节点删除失败：
	return false;
}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	bt.Erase(10);
	bt.InOrder();
	bt.Erase(8);
	bt.InOrder();
	return 0;
}

测试结果：

注意：

1.方法二的非递归删除函数，必须在调用删除函数删除minRight结点后，再将原待删除结点的值改为minRight的值，若逻辑顺序颠倒，则会导致在调用删除函数删除minRight结点时在二叉树当中存在两个满足要求的待删除结点。

2.非递归删除函数方法二和方法一在实现上只有一点不同，那就是处理待删除结点左右子树均不为空时的处理思路。

3.对于非递归删除函数的方法一和方法二来说，建议使用方法一，因为非递归删除函数方法二在删除左右子树均不为空的结点时，当找到minRight后还需要从二叉搜索树的根结点开始，重新遍历二叉树删除minRight结点。

递归实现

递归实现二叉搜索树的删除函数的思路如下：

1.若树为空树，则结点删除失败，返回false。
2.若所给key值小于树根结点的值，则问题变为删除左子树当中值为key的结点。
3.若所给key值大于树根结点的值，则问题变为删除右子树当中值为key的结点。
4.若所给key值等于树根结点的值，则根据根结点左右子树的存在情况不同，进行不同的处理。

而因为当待删除结点的左右子树均不为空时，处理方法有两种，所以删除函数的递归实现也有两种方法。

方法一：

方法一在遇到待删除结点的左右子树均不为空的情况时，采用的处理方法如下：

1.使用minParent标记根结点右子树当中值最小结点的父结点。
2.使用minRight标记根结点右子树当中值最小的结点。

当找到根结点右子树当中值最小的结点时，先根结点的值改为minRight的值，之后直接判断此时minRight是minParent的左孩子还是右孩子，然后对应让minParent的左指针或是右指针转而指向minRight的右孩子（注意：minRight的左孩子为空），最后将minRight结点进行释放即可。

//递归删除：
 //方法一：
bool _EraseR(Node*& root, const K& key)
{
	//空树：
	if (root == nullptr)
		return false;
	//key值小于根节点的值
	if (key < root->_key)
		//待删除节点在根节点的左子树
		return _EraseR(root->_left, key);
	//key值大于根节点的值
	else if (key > root->_key)
		//待删除节点在根节点的右子树
		return _EraseR(root->_right, key);
	//找到了，准备删除
	else
	{
		//待删除节点的左子树为空
		if (root->_left == nullptr)
		{
			//保存根节点
			Node* del = root;
			//根的右子树作为二叉树新的节点
			root = root->_right;
			delete del;
		}
		//待删除节点的右子树为空
		else if (root->_right == nullptr)
		{
			//保存根节点
			Node* del = root;
			//根的左子树作为二叉树新的节点
			root = root->_left;
			delete del;
		}
		else
		{
			//标记根节点右子树最左节点的父亲节点
			Node* minParent = root;
			//标记根节点右子树最左节点
			Node* minRight = root->_right;
			//寻找根节点右子树最左节点
			while (minRight->_left)
			{
				//往左走：
				minParent = minRight;
				minRight = minRight->_left;
			}
			//将根节点的值为minRight的值
			root->_key = minRight->_key;
			//注意一个隐含条件：此时minRight的_left为空
			if (minRight == minParent->_left) //minRight是其父结点的左孩子
			{
				minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
			}
			else //minRight是其父结点的右孩子
			{
				minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
			}
			delete minRight; //释放minRight
		}
		return true; //删除成功，返回true
	}
}
//递归删除：
bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	bt.EraseR(10);
	bt.InOrder();
	bt.EraseR(8);
	bt.InOrder();
	return 0;
}

方法二：

方法二在遇到待删除结点的左右子树均不为空的情况时的处理方式与方法一不同，方法二在找到待删除结点右子树当中值最小的结点后，先将minRight的值记录下来，然后再重新调用递归删除函数的子函数从当前根结点的右子树开始，删除右子树当中的minRight，当minRight被删除后再将根结点的值改为minRight的值，这样也完成了左右子树均不为空的结点的删除。

bool _EraseR(Node*& root, const K& key)
{
	//空树：
	if (root == nullptr)
		return false;
	//key值小于根节点的值
	if (key < root->_key)
		//待删除节点在根节点的左子树
		return _EraseR(root->_left, key);
	//key值大于根节点的值
	else if (key > root->_key)
		//待删除节点在根节点的右子树
		return _EraseR(root->_right, key);
	//找到了，准备删除
	else
	{
		//待删除节点的左子树为空
		if (root->_left == nullptr)
		{
			//保存根节点
			Node* del = root;
			//根的右子树作为二叉树新的节点
			root = root->_right;
			delete del;
		}
		//待删除节点的右子树为空
		else if (root->_right == nullptr)
		{
			//保存根节点
			Node* del = root;
			//根的左子树作为二叉树新的节点
			root = root->_left;
			delete del;
		}
		else
		{
			//标记根节点右子树最左节点
			Node* minRight = root->_right;
			//寻找根节点右子树最左节点
			while (minRight->_left)
			{
				//往左走：
				minRight = minRight->_left;
			}
			//记录minRight的值
			K minKey = minRight->_key;
			//删除右子树当中值为minkey的结点，即删除minRight
			_EraseR(root->_right, minKey);
			//将根结点的值改为minRight的值
			root->_key = minKey;
		}
		return true; //删除成功，返回true
	}
}

方法三：

方法三跟之前两种方法更简洁，可以转换成在子树去递归删除。

bool _EraseR(Node*& root, const K& key)
{
	if (root == nullptr)
		return false;

	if (root->_key < key)
	{
		return _EraseR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _EraseR(root->_left, key);
	}
	else
	{
		// 删除
		if (root->_left == nullptr)
		{
			Node* del = root;
			root = root->_right;
			delete del;
			return true;
		}
		else if (root->_right == nullptr)
		{
			Node* del = root;
			root = root->_left;
			delete del;

			return true;
		}
		else
		{
			Node* subLeft = root->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}
			swap(root->_key, subLeft->_key);
			//精髓所在：
			// 转换成在子树去递归删除
			return _EraseR(root->_right, key);
		}
	}
}

注意：

1.实现递归删除函数时，不论是方法一还是方法二，递归删除函数子函数接收root参数时必须采用引用接收，否则无法完成二叉树当中各个结点的连接关系。

2.递归删除函数的方法二和方法一在实现上也只有一点不同，那就是处理待删除结点左右子树均不为空时的处理思路。

3.对于递归删除函数的方法一和方法二来说，建议使用方法二，因为方法二在删除左右子树均不为空的结点时，当找到minRight后就无需从二叉搜索树的根结点开始，重新遍历二叉树删除minRight结点了，并且递归删除函数方法二写法的可读性更高。

查找函数

根据二叉搜索树的特性，我们在二叉搜索树当中查找指定值的结点的方式如下：

1.若树为空树，则查找失败，返回nullptr。
2.若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
3.若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
4/若key值等于当前结点的值，则查找成功，返回对应结点的地址。

非递归实现

二叉搜索树查找函数的非递归实现如下：

    //非递归查找：
   bool Find(const K& key)
    {
	   Node* cur = _root;
	   while (cur)
	   {
		   if (key > cur->_key)
		   {
			   cur = cur->_right;
		   }
		   else if (key < cur->_key)
		   {
			   cur = cur->_left;
		   }
		   else
			   return true;
	   }
	   return false;
    }

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	cout << endl;
	int n = 0;
	cout << "请输入要查找的节点值：" << endl;
	cin >> n;
	int ret=bt.Find(n);
	cout << "查找结果为：" << endl;
	cout << ret<< endl ;
	return 0;
}

测试结果：

递归实现

二叉搜索树查找函数的递归实现如下：

 //递归查找：
 bool FindR(const K& key)
 {
  return _FindR(_root, key);
 }
 
	//递归查找
	bool _FindR(Node* root, const K& key)
	{
		//树为空
		if (root == nullptr)
			return false;
		if (key < root->_key)
			return _FindR(root->_left,key);
		else if (key > root->_key)
			return _FindR(root->_right,key);
		else
			return true;
	}

测试一下：

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> bt;
	for (auto e : a)
	{
		bt.InsertR(e);
	}
	bt.InOrder();
	cout << endl;
	int n = 0;
	cout << "请输入要查找的节点值：" << endl;
	cin >> n;
	int ret=bt.FindR(n);
	cout << "查找结果为：" << endl;
	cout << ret<< endl ;
	return 0;
}

测试结果：

二叉搜索树的应用

K模型

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
1.以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

2.在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

这里我们以水果举例：我们可以通过key模型来检查水果在不在。

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

测试结果：

KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

1.比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对；

2.再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是<word, count>就构成一种键值对。

void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	kv::BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		kv::BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_value << endl;
		}
	}
}

二叉搜索树的性能分析

对于二叉搜索树来说，无论的插入查找还是删除操作，都需要先进行查找，因此查找的效率代表了二叉搜索树中各个操作的性能。

对于二叉搜索树这棵特殊的二叉树，我们每进行一次查找，若未查找到目标结点，则还需查找的树的层数就减少了一层，所以我们最坏情况下需要查找的次数就是二叉搜索树的深度，深度越深的二叉搜索树，比较的次数就越多。

对于有n个结点的二叉搜索树：

最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

而时间复杂度描述的是最坏情况下算法的效率，因此普通二叉搜索树各个操作的时间复杂度都是O(N)。

所以实际上，二叉搜索树在极端情况下是没办法保证效率的，因此由二叉搜索树又衍生出来了AVL树、红黑树等，它们对二叉搜索树的高度进行了优化，使得二叉搜索树非常接近完全二叉树，因此对于这些树来说，它们的效率是可以达到O(logN)的。