【ONE·C++ || 二叉搜索树】

总言

  二叉树进阶：主要介绍二叉搜索树相关内容。

1、基本介绍

1.1、什么是二叉搜索树

  1）、概念与性质介绍
  二叉搜索树又称二叉排序树，它可以是一棵空树，也可以是具有以下性质的二叉树:
  1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
  2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
  3、它的左右子树也分别为二叉搜索树。

  
  
  2）、二叉搜索树的这种性质为其来带什么优势？
  在查找效率方面，由于二叉搜索树左子树都比根小，右子树都比根大，这种一分为二的效果在查找方面提供了效率，时间复杂度为O(h)，其中h为高度。
  
  
  3）、一些需要注意的点
  1、二叉搜索树是不允许有重复的值出现的
  2、增删查改中，二叉搜索树不允许随意修改，因此在功能实现上，我们只进行增删查的操作。
  
  

2、相关实现

2.1、基本框架

2.1.1、如何构建二叉树单节点

  创建单个节点的结构，与之前链式二叉树中内容基本一致，每个结点由数据域和左右指针域组成，只是这里我们借助了模板。

template<class K>
class BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

  
  由于后续需求，我们在这里先将其构造函数写上。注意对参数的理解：const K& key = K()。

template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key = K())
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

  由后续内容，BSTreeNode会在类外调用，故而我们可将其实现为struct。
  
  

2.1.2、如何定义一个二叉搜索树

  大致框架不变，只是加入了类与模板，另外需要注意它有一个根节点Node* _root = nullptr;，这里给根节点赋了一个缺省值，实际作用于初始化列表中。

template<class K>
class BinarySearchTree
{
	typedef BinarySearchTree<K> BSTree;
	typedef BSTreeNode<K> Node;

	//……

private:
	Node* _root = nullptr;

};

  接下来是完善其各个成员函数。
  
  
  

2.2、非递归实现：插入、查找、删除

2.2.1、二叉搜索树·插入：Insert

  1）、基本说明
  需求说明： 在二叉搜索树中插入一个新的值，保持插入前后，仍旧满足二叉搜索树的性质（左子树比根小，右子树比根大）。
  
  根据上述需求，需要思考：
  1、如何找到相应的插入位置？
  2、如何将新增节点与原先二叉树链接上？
  
  对于问题一：
  a、若树为空，则直接新增节点，赋值给root；
  b、若树不为空，从根节点开始，依次让当前节点值与待插入值val比较，若待插入值大于当前节点值，则说明其要放在当前节点值右侧子树中；若小于，则说明其要放在当前节点值左侧子树中；若等于，则说明二叉搜索树中已存在该值，不必插入（二叉搜索树不允许）；
  c、如此重复判断比较，直到当前节点值与待插入值相同时返回，或者当前节点左孩子/右孩子为空时，插入。

  
  insert实现1.0：

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		while (cur)
		{
			if (key > cur->_key)//当前节点值比待插入值小
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)//当前节点值比待插入值大
			{
				cur = cur->_left;
			}
			else//二者相同，直接返回
			{
				return false;
			}
		}

		//当while循环结束时，cur==nullptr，此时插入相应值
		cur = new Node(key);
		return true;
	}

  
  对于问题二：
  a、观察上述代码，我们只完成在相应位置新增节点，由于cur是临时变量，出了函数作用域就销毁，故该节点与原先二叉树并没有实际链接上。这也是我们上述要思考的问题之一，如何将新增节点与原先二叉树链接上？

  解决方案如下： 记录cur的父节点。需要注意，这里要判断新增的cur对于其parent而言是左孩子还是右孩子。

  
  insert实现2.0：

template<class K>
class BinarySearchTree
{
public:
	typedef BinarySearchTree<K> BSTree;
	typedef BSTreeNode<K> Node;
	
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//二者相同，直接返回
			{
				return false;
			}
		}

		//当while循环结束时，cur==nullptr，此时插入相应值
		cur = new Node(key);
		//与原二叉树链接
		if (key > parent->_key)
			parent->_right = cur;
		else
			parent->_left = cur;
			
		return true;
	}

	//……
	
};

  注意事项：
  我们说过，最后链接时，需要注意parent和cur的关系，这里我们是用parent->_key与cur->_key进行左右子树判断的。这样判断出的结果能满足二叉搜索树。

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

  一种错误写法如下：不能直接用父节点左右孩子是否为空进行判断。举例：左孩子为空不一定满足待插入值一定比父节点值小。此外，我们还有可能遇到parent左右孩子都为空时，这时候也不是说可以左右孩子任意链接，我们始终都要保持左比父小、右比父大的特性。

		if (parent->_left == nullptr)
			parent->_left = cur;
		else
			parent->_right = cur;

2.2.2、二叉搜索树·中序遍历：InOrder

  1）、基本说明
  实现说明：为二叉搜索树写一个中序遍历函数，可以方便我们遍历查看二叉搜索树的值。

  问题：为什么选择中序遍历，而不是前序或者后续？
  回答： 一个直接原因是二叉搜索树的性质，左子树都比根小，右子树都比根大，那么我们在中序遍历时，访问顺序是左子树、根、右子树，就能直观清晰的看到一个有序的二叉搜索树，便于后续观察与检测。
  
  相关实现如下：

template<class K>
class BinarySearchTree
{
public:
	//……

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	//……

};

  说明：InOrder和_InOrder，为什么要进行一个封装操作？
  回答：假如我们直接使用_InOrder，其有一参数root需要我们传递根节点，但是_root为私有成员，我们在类外无法直接调用，所需需要想办法解决传参问题。（PS：此处的root是每次递归遍历时，当前位置的节点，并非整个二叉树的根节点）

  
  解决方案：
  1、在类中实现一个getroot()函数，参考日期类获取年、月、日。
  2、将test01设置为BinarySearchTree的友元函数，可以访问类的私有成员。（不推荐）
  3、如上述，再封装一层，我们直接调用公有的InOerder。
  
  
  2）、验证插入Insert
  相关代码如下：

void test01()
{
	int a[] = { 8,3,1,10,6,4,7,14,13,14,13,7,4 };
	BinarySearchTree<int> tree;
	for (auto e : a)
	{
		tree.Insert(e);
	}
	tree.InOrder();
}

  验证结果如下：事实上这里InOrder与Insert结合，有天然去重和排序的效果。

  
  
  
  

2.2.3、二叉搜索树·查找：Find

  说明：在二叉搜索树中查找某一个值key。
  
  相关实现如下：

	bool Find(const K& key)
	{
		Node* cur = _root;//此处不用单独判断_root是否为空
		while (cur)
		{
			if (key < cur->_key)
				cur = cur->_left;
			else if (key > cur->_key)
				cur = cur->_right;
			else
				return true;
		}

		return false;
	}

2.2.4、二叉搜索树·删除：Erase

  1）、思路分析
  情况一：要删除的结点无孩子结点/单孩子结点
  处理方法：直接删除，但需要注意将待删除结点的孩子结点与其父结点建立新联系。

  要删除的结点有左、右孩子结点时：替换法，从左右子树中找出一个适合的值，进行替换，然后删除。
  1、可有以下两种处理方法：
    a、找左子树中最大值，这样能保证交换后，根节点仍旧大于其左子树、小于其右子树。左子树中最大值即其最右边的值。
    b、找右子树中最小值，这样能保证交换后，根节点仍旧大于其左子树、小于其右子树。右子树中最小值即其最左边的值。
  2、找到后与待删节点替换，这样对于待删节点，其处理方法和上述单结点/无孩子结点一致。（原因：如果替换后仍旧为双孩子，那么就不满足左子树最右、右子树最左的条件，也就不是我们要寻找的值。）

  
  
  2）、写法如下
  1、先寻找待删除结点：

	bool Erase(const K& key)
	{
		//查找key值
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)//待删除值比当前值大，向右子树找
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)//待删除值比当前值小，向左子树找
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//key==cur->_key,找到则删除n
			}
		}
		//找不到：
		return false;
	}

  
  2、对于单孩子结点、无孩子结点的情况：

				//处理单结点/无结点
				if (cur->_left == nullptr)//待删结点的左孩子为空，说明其只有右孩子或者无左右孩子
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)//cur为parent的左孩子时
						{
							parent->_left = cur->_right;
						}
						else//cur为parent的右孩子时
						{
							parent->_right = cur->_right;
						}
					}

				}
				else if (cur->_right == nullptr)//待删结点的右孩子为空，说明其只有左孩子或者无左右孩子
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)//cur为parent的左孩子时
						{
							parent->_left = cur->_left;
						}
						else//cur为parent的右孩子时
						{
							parent->_right = cur->_left;
						}
					}

				}

  细节理解： 以下情况是为了解决上述情况中，待删结点为根节点时：

					if (cur == _root)
					{
						_root = cur->_right;
					}

					if (cur == _root)
					{
						_root = cur->_left;
					}

  
  
  
  
  3、对于待删结点存在左右孩子时：

				else//左右孩子都存在时：以找右子树最小值为替换值，即先找到右子树最左结点
				{
					Node* Min = cur->_right;
					Node* MinParent = cur;
					while (Min->_left)
					{
						MinParent = Min;
						Min = Min->_left;
					}
					//找到后，交换值
					std::swap(Min->_key, cur->_key);
					//右树最左值，其孩子结点只能是右孩子或直接无孩子结点，它不可能存在左孩子
					if (MinParent->_left == Min)
					{
						MinParent->_left = Min->_right;
					}
					else
					{
						MinParent->_right = Min->_right;
					}

					delete Min;
				}

  细节理解：

					if (MinParent->_left == Min)
					{
						MinParent->_left = Min->_right;
					}
					else
					{
						MinParent->_right = Min->_right;
					}

  
  
  
  
  3）、整体情况和测试
  整体代码实现如下：

	bool Erase(const K& key)
	{
		//查找key值
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//key==cur->_key,找到则删除
			{
				//处理单结点/无结点
				if (cur->_left == nullptr)//左孩子为空，右孩子有或无
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)//cur为parent的左孩子时
						{
							parent->_left = cur->_right;
						}
						else//cur为parent的右孩子时
						{
							parent->_right = cur->_right;
						}
					}

				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

				}
				else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点
				{
					Node* Min = cur->_right;
					Node* MinParent = cur;
					while (Min->_left)
					{
						MinParent = Min;
						Min = Min->_left;
					}
					//找到后，交换值，
					std::swap(Min->_key, cur->_key);
					//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子
					if (MinParent->_left == Min)
					{
						MinParent->_left = Min->_right;
					}
					else
					{
						MinParent->_right = Min->_right;
					}

					delete Min;
				}
				return true;

			}
		}
		//找不到：
		return false;
	}

  测试如下：

void test02()
{
	int a[] = { 8,3,1,10,6,4,7,14,13};
	BinarySearchTree<int> tree;
	for (auto e : a)
	{
		tree.Insert(e);
	}
	tree.InOrder();
	cout << endl;

	cout << endl;
	cout<< "测试Find：" << endl;
	cout << tree.Find(8) << endl;
	cout << tree.Find(13) << endl;

	cout << endl;
	cout << "测试Erase：" << endl;
	for (auto e : a)
	{
		tree.Erase(e);
		tree.InOrder();
		cout << endl;
	}
	cout << endl;
}

2.3、递归实现：插入、查找、删除

2.3.1、二叉搜索树·递归查找：FindR

  同理，使用递归需要涉及根节点，其为私有成员，因此我们在这进行一层封装。相关实现如下：
  1、若递归到当前结点为空，则二叉树中没有该值；
  2、若目标值比当前结点值大，则到其右子树找；若目标值比当前结点小，则到其左子树找；若目标值等于当前结点值，则说明找到。
  

public:
	二叉树·递归查找·封装
	bool FindR(const K& key)
	{
		return _FindR(_root,key);
	}


private:
	二叉树·递归查找
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
				return _FindR(root->_right, key);
			else if (root->_key > key)
				return _FindR(root->_left, key);
			else
				return true;
		}

  
  结果验证如下：

  测试代码：

void test03()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	BinarySearchTree<int> tree;
	for (auto e : a)
	{
		tree.Insert(e);
	}
	tree.InOrder();
	cout << endl;


	cout << tree.FindR(14) << endl;
	cout << tree.FindR(12) << endl;
}

2.3.2、二叉搜索树·递归插入：InsertR

  相关实现如下：
  1、若当前结点为空，说明我们找到了合适的插入位置；
  2、若待插入值比当前结点值大，则递归来到右子树寻找适合位置；若待插入值比当前结点值小，则递归来到左子树寻找适合位置。
  3、若待插入值和当前结点值相等，根据二叉搜索树元素不重复特性，直接返回不插入值。

	二叉树·递归插入·封装
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}


private:
	二叉树·递归插入
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key > root->_key)
			return _InsertR(root->_right, key);
		else if (key < root->_key)
			return _InsertR(root->_left, key);
		else
			return false;
	}

  
  细节理解：Node*& root,，为什么这里对root进行了引用处理?
  回答： 根据上述递归，最后我们找到合适的插入位置时(root==nullptr)，此时我们通过new新增结点，但这里存在一个问题，如果是bool _InsertR(Node* root, const K& key)，root形参为临时变量，在层层递归中并不能与我们实际的二叉树建立联系。因此，这里使用引用，主要目的是新增结点后，要让其与原先二叉树链接上。

  
  
  验证结果如下：

void test04()
{
	int a[] = { 8,3,1,10,6,4,7,14,13,13,14,7,4 };
	BinarySearchTree<int> tree;
	for (auto e : a)
	{
		tree.InsertR(e);
	}
	tree.InOrder();
	cout << endl;
}

2.3.3、二叉搜索树·递归删除：EraseR

  相关实现如下：
  1、若当前结点为空，则说明该树中无待删除值；
  2、若待删除值比当前结点值大，则递归来到右子树寻找树中是否有待删除值；若待删除值比当前结点值小，则递归来到左子树寻找树中是否有待删除值。
  3、若待删除值和当前结点值相等，说明找到待删除值所在结点。此时面临的删除情况与非递归时一致。

private:
	二叉树·递归删除·封装
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}


private:
	二叉树·递归删除·封装
	bool _EraseR(Node*& root,const K& key)
	{
		//查找值
		if (root == nullptr)
			return false;
		if (key > root->_key)
			return _EraseR(root->_right, key);
		else if (key < root->_key)
			return _EraseR(root->_left, key);
		else//root->key==key，找到待删结点，删除面临的情况和非递归一致
		{
			Node* tmp = root;
			//只有单孩子结点、无孩子结点
			if (root->_left == nullptr)
				root = root->_right;
			else if (root->_right == nullptr)
				root = root->_left;
			else//待删结点有左右两孩子结点，替换法，此处以找右子树的最小值做替换
			{//右子树最小值即右子树最左值，其特点是没有左孩子，可能有右孩子
				Node* Min = root->_right;
				while (Min->_left)
					Min = Min->_left;
				std::swap(Min->_key, root->_key);
				return _EraseR(root->_right, key);
				//错误写法：Erase(key),替换后已经不符合搜索二叉树了。
			}
			delete tmp;
			return true;
		}
	}

  
  演示结果如下：

  
  
  
  

2.4、基本成员函数：构造、拷贝、赋值、析构

2.4.1、析构：~BinarySearchTree()、销毁：_Destory

  说明：由于二叉搜索树中，每个结点都是new动态申请出来的，因此，析构时需要对每结点都进行处理，这里我们顺便实现一个_Destory函数，其作用是释放每个结点。

public：
	二叉树·析构
	~BinarySearchTree()
	{
		_Destory();
	}


private:
	//二叉树·销毁
	void _Destory(Node*& root)
	{
		if (root == nullptr)
			return;
		_Destory(root->_left);//销毁孩子结点
		_Destory(root->_right);
		delete root;//销毁根结点
		root = nullptr;
	}

  Node*& root，这里传递引用，是因为后续root = nullptr;，实参root要置空，则不能只是传值传参。

  若不对其做处理，情况如下：

	void _Destory(Node* root)
	{
		if (root == nullptr)
			return;
		_Destory(root->_left);//销毁孩子结点
		_Destory(root->_right);
		delete root;//销毁根结点
	}

2.4.2、拷贝构造、构造：BinarySearchTree（default关键字）

  说明：如何用已经生成的二叉搜索树去构造一个新的二叉搜索树呢？首先，如果使用InOerder+Insert结合，遍历被拷贝的二叉搜索树，然后将其每一个值插入，这种方法行不通，因为二叉搜索树的生成依赖于其顺序。

  那么是否还有其它方法？此处我们只能遍历已经二叉搜索树，根据其每个结点，依次new新结点，并确定其左右孩子关系。
  

public:
	二叉树·拷贝构造
	BinarySearchTree(const BinarySearchTree<K>& tree)
	{
		_root = _Copy(tree._root);
	}

private:

	//二叉树·前序拷贝
	Node* _Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* copyRoot = new Node(root->_key);//对当前根节点new新空间，拷贝数值
		copyRoot->_left=_Copy(root->_left);//对其左孩子进行拷贝
		copyRoot->_right = _Copy(root->_right);//对其右孩子进行拷贝
		return copyRoot;
	}

  
  上述代码如果直接运行会报错：

  这是因为我们没有实现默认的构造函数。根据相关内容，如果我们显示写构造函数，那么编译器就不会生成默认构造函数。而拷贝构造也是构造函数中的一种，相当于我们显示写了构造，故而此处缺少默认构造函数，解决方法有如下两种：

	//二叉树·构造：我们自己显示写一个默认构造函数
	BinarySearchTree()
	{}

	//二叉树·构造：使用关键字强制生成默认构造
	BinarySearchTree() = default;

2.4.3、赋值

	二叉树·赋值运算符重载
	BinarySearchTree<K>& operator=(BinarySearchTree<K> tree)//直接复用构造函数
	{
		std::swap(_root, tree._root);
		return *this;
	}

  
  
  验证代码如下:

void test06()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	BinarySearchTree<int> tree;
	for (auto e : a)
	{
		tree.Insert(e);
	}
	tree.InOrder();
	cout << endl;

	//验证拷贝构造
	BinarySearchTree<int> tree2(tree);
	tree2.InOrder();
	cout << endl;

	//验证赋值运算符重载
	BinarySearchTree<int> tree3;
	tree3 = tree;
	tree3.InOrder();
	cout << endl;
}

  验证结果如下：

3、整体预览

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

template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key = K())
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

template<class K>
class BinarySearchTree
{
public:
	//typedef BinarySearchTree<K> BSTree;
	typedef BSTreeNode<K> Node;

	
	二叉树插入
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)//当前节点值比待插入值小
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)//当前节点值比待插入值大
			{
				parent = cur;
				cur = cur->_left;
			}
			else//二者相同，直接返回
			{
				return false;
			}
		}

		//当while循环结束时，cur==nullptr，此时插入相应值
		cur = new Node(key);
		if (key > parent->_key)
			parent->_right = cur;
		else
			parent->_left = cur;
		//if (parent->_left == nullptr)//error
		//	parent->_left = cur;
		//else
		//	parent->_right = cur;
		return true;
	}

	二叉树查找
	bool Find(const K& key)
	{
		//if (_root == nullptr)
		//	return false;
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key)
				cur = cur->_left;
			else if (key > cur->_key)
				cur = cur->_right;
			else
				return true;
		}

		return false;
	}


	//二叉树删除
	bool Erase(const K& key)
	{
		//查找key值
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//key==cur->_key,找到则删除
			{
				//处理单结点/无结点
				if (cur->_left == nullptr)//左孩子为空，右孩子有或无
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)//cur为parent的左孩子时
						{
							parent->_left = cur->_right;
						}
						else//cur为parent的右孩子时
						{
							parent->_right = cur->_right;
						}
					}

				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

				}
				else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点
				{
					Node* Min = cur->_right;
					Node* MinParent = cur;
					while (Min->_left)
					{
						MinParent = Min;
						Min = Min->_left;
					}
					//找到后，交换值，
					std::swap(Min->_key, cur->_key);
					//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子
					if (MinParent->_left == Min)
					{
						MinParent->_left = Min->_right;
					}
					else
					{
						MinParent->_right = Min->_right;
					}

					delete Min;
				}
				return true;

			}
		}
		//找不到：
		return false;
	}


	//void _InOrder(Node* root)//演示封装原因
	//{
	//	if (root == nullptr)
	//		return;

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


	二叉树中序遍历·封装
	void InOrder()
	{
		_InOrder(_root);
	}


	二叉树·递归查找·封装
	bool FindR(const K& key)
	{
		return _FindR(_root,key);
	}

	二叉树·递归插入·封装
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	二叉树·递归删除·封装
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

	二叉树·析构
	~BinarySearchTree()
	{
		_Destory(_root);
	}

	//二叉树·构造
	//BinarySearchTree()
	//{}

	//二叉树·构造：使用关键字强制生成默认构造
	BinarySearchTree() = default;

	二叉树·拷贝构造
	BinarySearchTree(const BinarySearchTree<K>& tree)
	{
		_root = _Copy(tree._root);
	}

	二叉树·赋值运算符重载
	BinarySearchTree<K>& operator=(BinarySearchTree<K> tree)
	{
		std::swap(_root, tree._root);
		return *this;
	}

private:

	//二叉树·前序拷贝
	Node* _Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* copyRoot = new Node(root->_key);
		copyRoot->_left=_Copy(root->_left);
		copyRoot->_right = _Copy(root->_right);
		return copyRoot;
	}

	//二叉树·销毁
	void _Destory(Node*& root)
	{
		if (root == nullptr)
			return;
		_Destory(root->_left);//销毁孩子结点
		_Destory(root->_right);
		delete root;//销毁根结点
		root = nullptr;
	}


	二叉树·递归删除·封装
	bool _EraseR(Node*& root,const K& key)
	{
		//查找值
		if (root == nullptr)
			return false;
		if (key > root->_key)
			_EraseR(root->_right, key);
		else if (key < root->_key)
			_EraseR(root->_left, key);
		else//root->key==key，找到待删结点，删除面临的情况和非递归一致
		{
			Node* tmp = root;
			//只有单孩子结点、无孩子结点
			if (root->_left == nullptr)
				root = root->_right;
			else if (root->_right == nullptr)
				root = root->_left;
			else//待删结点有左右两孩子结点，替换法，此处以找右子树的最小值做替换
			{//右子树最小值即右子树最左值，其特点是没有左孩子，可能有右孩子
				Node* Min = root->_right;
				while (Min->_left)
					Min = Min->_left;
				std::swap(Min->_key, root->_key);
				return _EraseR(root->_right, key);
				//错误写法：Erase(key),替换后已经不符合搜索二叉树了。
			}
			delete tmp;
			return true;
		}
	}



	二叉树·递归插入
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key > root->_key)
			return _InsertR(root->_right, key);
		else if (key < root->_key)
			return _InsertR(root->_left, key);
		else
			return false;
	}

	二叉树·递归查找
	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;
	}

	二叉树中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

	Node* _root = nullptr;

};

4、二叉搜索树运用说明

4.1、二叉搜索树性能简述

  1）、二叉搜索树增删查时间复杂度
  二叉搜索树增删查中，插入和删除操作都必须先查找，因此查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
  时间复杂度$O(h)$，最坏情况$h=N$（单支）。
  
  2）、针对其的改进
  平衡树：红黑树、AVL树等。
  
  

4.2、应用介绍

4.2.1、K模型和KV模型说明

  1）、二叉搜索树的两个模型介绍
  1、K模型：只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
  样例举例：K模型主要运用于判断关键字key在与不在。如刷卡进学校、进宿舍楼；检查一篇英文文档中单词拼写错误。
  
  
  2、KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
  样例举例：KV模型主要是通过key找对应的value。如中英字词匹配；高铁站买票刷身份证通过；统计某类事物出现次数。
  
  

4.2.2、使用举例

  1）、部分框架说明
  这里我们演示KV模型，相应的，我们需要对之前的二叉搜索树做一些修改，部分框架实现如下：简单来讲就是多加了一个模板参数value。

namespace keyvalue
{
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode(const K& key = K(),const V& value=V())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}

		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
	};

	template<class K,class V>
	class BinarySearchTree
	{
	public:
		typedef BSTreeNode<K,V> Node;

		二叉树插入
		bool Insert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}

			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)//当前节点值比待插入值小
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)//当前节点值比待插入值大
				{
					parent = cur;
					cur = cur->_left;
				}
				else//二者相同，直接返回
				{
					return false;
				}
			}

			//当while循环结束时，cur==nullptr，此时插入相应值
			cur = new Node(key,value);
			if (key > parent->_key)
				parent->_right = cur;
			else
				parent->_left = cur;
			return true;
		}


		二叉树查找
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
					cur = cur->_left;
				else if (key > cur->_key)
					cur = cur->_right;
				else
					return cur;
			}

			return cur;
		}


		//二叉树删除
		bool Erase(const K& key)
		{
			//查找key值
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else//key==cur->_key,找到则删除
				{
					//处理单结点/无结点
					if (cur->_left == nullptr)//左孩子为空，右孩子有或无
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)//cur为parent的左孩子时
							{
								parent->_left = cur->_right;
							}
							else//cur为parent的右孩子时
							{
								parent->_right = cur->_right;
							}
						}

					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

					}
					else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点
					{
						Node* Min = cur->_right;
						Node* MinParent = cur;
						while (Min->_left)
						{
							MinParent = Min;
							Min = Min->_left;
						}
						//找到后，交换值，
						std::swap(Min->_key, cur->_key);
						//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子
						if (MinParent->_left == Min)
						{
							MinParent->_left = Min->_right;
						}
						else
						{
							MinParent->_right = Min->_right;
						}

						delete Min;
					}
					return true;

				}
			}
			//找不到：
			return false;
		}



		二叉树中序遍历·封装
		void InOrder()
		{
			_InOrder(_root);
		}


		二叉树·析构
		~BinarySearchTree()
		{
			_Destory(_root);
		}

	private:

		//二叉树·销毁
		void _Destory(Node*& root)
		{
			if (root == nullptr)
				return;
			_Destory(root->_left);//销毁孩子结点
			_Destory(root->_right);
			delete root;//销毁根结点
			root = nullptr;
		}


		二叉树中序遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

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

		Node* _root = nullptr;

	};
}

  
  2）、样例演示一：输入英文，查找对应中文
  演示代码如下：

void testKV01()
{
	建立一个中英词典：
	keyvalue::BinarySearchTree<string, string> dict;
	dict.Insert("conceal", "v.隐藏");
	dict.Insert("breakdown", "n.崩溃");
	dict.Insert("clutch", "v.抓住");
	dict.Insert("philosopher", "n.哲学家");
	dict.Insert("stamp", "n.邮票");

	//查找词：给key值，获取value值
	string str;
	while (cin >> str)
	{
		//记录查找的结果
		keyvalue::BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret)
		{
			cout << "中文: " << ret->_value << endl;
		}
		else
		{
			cout << "查无此词" << endl;
		}

		cout << endl;
	}
}

  
  
  
  
  2）、样例演示二：统计一段时间内不同天气出现次数
  
  演示代码如下：

void testKV02()
{
	//将天气存入二叉搜索树中
	string arr[] = { "晴","多云","晴","阴","小雨","多云","多云","阴","晴","小雨","大雨","阴","多云","晴" };
	keyvalue::BinarySearchTree<string, int> countTree;
	for (auto& str : arr)
	{
		//查找countTree中有没有匹配的天气
		keyvalue::BSTreeNode<string, int>* ret = countTree.Find(str);
		if (ret)
		{
			ret->_value++;//若有，直接修改计数值
		}
		else
		{
			countTree.Insert(str, 1);//若无，先将对应天气存入二叉搜索树中
		}
	}

	countTree.InOrder();
	cout << endl;
}

  
  
  
  
  
  
  
  
  文章来源地址https://www.toymoban.com/news/detail-432705.html

到了这里，关于【ONE·C++ || 二叉搜索树】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！