C++ 二叉搜索树(BST)的实现(非递归版本与递归版本)与应用

C++ 二叉搜索树的实现与应用

• 一.二叉搜索树的特点
• 二.我们要实现的大致框架
• 三.Insert
• 四.InOrder和Find
• • 1.InOrder
  • 2.Find
  • 五.Erase
  • 六.Find,Insert,Erase的递归版本
  • • 1.FindR
    • 2.InsertR
    • 3.EraseR
    • 七.析构,拷贝构造,赋值运算符重载
    • • 1.析构
      • 2.拷贝构造
      • 3.赋值运算重载
      • 八.Key模型完整代码
      • 九.二叉搜索树的应用
      • • 1.Key模型
        • 2.Key-Value模型

          二叉搜索树既可以实现为升序版本,也可以实现为降序版本

          本文实现为升序版本

          一.二叉搜索树的特点

          二叉搜索树是一种特殊的二叉树

          它的特点是:

          1.左子树的所有节点均比根节点的值小

          2.右子树的所有节点均比根节点的值大

          3.左右子树都是二叉搜索树

          4.中序遍历序列是有序的

          5.一般二叉搜索树不允许有重复值

          当然,二叉搜索树默认是升序的,不过也可以实现成降序的样子

          只需要更改一下第1条和第2条即可,

          第一条改为左子树的节点都要大于根节点

          第二条改为右子树的节点都要小于根节点

          此时实现出来的二叉搜索树就是降序的

          

          例如:这个树就是一个二叉搜索树

          二.我们要实现的大致框架

          #pragma once
          #include 
          using namespace std;
          //BST排升序:左孩子小于我,  右孩子大于我
          //排降序:   左孩子大于我,  右孩子小于我
          //节点的结构体
          template 
          struct BSTreeNode
          {
          	BSTreeNode* _left = nullptr;
          	BSTreeNode* _right = nullptr;
          	K _key;
          	BSTreeNode(const K& key)
          		:_key(key)
          	{}
          };
          template
          class BSTree
          {
          	typedef BSTreeNode Node;
          public:
          	//非递归实现insert.find,erase
          	bool Insert(const K& key);
          	Node* Find(const K& key);
          	bool Erase(const K& key);
          	//析构函数  后续遍历析构
          	~BSTree();
          	
          	//C++11新语法
          	BSTree() = default;//强制生成默认构造
          	
          	//拷贝构造
          	//先序遍历构造
          	BSTree(const BSTree& bst);
          	//赋值运算符重载:现代版本
          	BSTree& operator=(BSTree bst);
          	void InOrder()
          	{
          		_InOrder(_root);
          	}
          	//递归实现insert.find,erase
          	Node* 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);
          	}
          	
          private:
          	//拷贝构造函数的子函数
          	Node* _Copy(const Node* root);
          	//析构函数的子函数
          	void _Destroy(Node*& root);
          	//中序遍历的子函数
          	void _InOrder(Node* root);
          	//find的子函数
          	Node* _FindR(Node* root, const K& key);
          	//insert的子函数
          	bool _InsertR(Node*& root, const K& key);
          	//erase的子函数
          	bool _EraseR(Node*& root, const K& key);
          	
          	//给根节点_root缺省值nullptr
          	Node* _root = nullptr;
          };
          

          这是Key模型的版本,最后我们要修改一份Key-Value版本

          template 
          

          这里模板给K的原因是:贴合K模型而已,所以没有用T

          这里的R : recursion(递归的英文)

          //给根节点_root缺省值nullptr
          Node* _root = nullptr;
          

          这里直接给根节点_root缺省值nullptr了,编译器默认生成的构造函数就会使用这个缺省值

          这里补充一点:

          //C++11新语法:给default这个关键字增加了一个含义
          BSTree() = default;//强制生成默认构造
          

          三.Insert

          学习了二叉搜索树的特点之后,我们来看如何插入一个值

          

          注意:

          1.在遍历查找要插入的位置时一定要记录父节点,否则无法插入

          2.最后插入的时候要判断该值与父节点的大小关系,这样才能知道要插入到左侧还是右侧

          因此我们就可以写出这样的代码

          插入成功,返回true
          插入失败(说明插入了重复值),返回false
          bool Insert(const K& key)
          {
          	if (_root == nullptr)
          	{
          		_root = new Node(key);
          		return true;
          	}
          	Node* cur = _root;
          	Node* parent = _root;//记录父亲,因为要能够插入
          	while (cur)
          	{
          		//要插入的值小于父亲,往左找
          		if (cur->_key > key)
          		{
          			parent = cur;
          			cur = cur->_left;
          		}
          		//要插入的值大于父亲,往右找
          		else if (cur->_key < key)
          		{
          			parent = cur;
          			cur = cur->_right;
          		}
          		//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回false
          		else
          		{
          			return false;
          		}
          	}
          	//此时cur为空,说明找到了空位置 在此位置插入value
          	cur = new Node(key);
          	//要插入的元素小于父亲,插入到左侧
          	if (parent->_key > key)
          	{
          		parent->_left = cur;
          	}
          	//要插入的元素大于父亲,插入到右侧
          	else
          	{
          		parent->_right = cur;
          	}
          	//插入成功
          	return true;
          }
          

          四.InOrder和Find

          1.InOrder

          关于InOrder中序遍历跟普通二叉树的中序遍历是一模一样的

          只不过因为要用递归去实现,而且_root是私有变量不能让外界访问到,因此封装了一个子函数,让子函数去递归完成任务,主函数可以被外界调用到,子函数无需提供给外界

          同理,后面的Insert,Erase,Find的递归版本都是封装了一个子函数,跟InOrder这方面的思路一样

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

          2.Find

          学习了Insert之后,Find对我们来说就很简单了

          要查找一个值key

          1.key小于当前节点的值,往左找

          2.key大于当前节点的值,往右找

          3.key等于当前节点的值,找到了,返回该节点

          4.要查找的当前节点为空节点,返回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 cur;
          		}
          	}
          	//此时cur为空说明没有找到
          	return nullptr;
          }
          

          此时我们就可以开始玩这个二叉搜索树了

          

          可以看出,中序遍历的确是有序的

          五.Erase

          前面的insert和find都比较简单,接下来的erase就比较复杂了

          erase分为4种情况:

          对于要删除的节点

          1.该节点没有左孩子,也没有右孩子

          

          不过这里最后删除的时候是不对的,因为14依旧指向13,而13已经被释放了,所以14的_left指针就成为了野指针,怎么办呢?

          此时只需要先让该节点的父亲(也就是14)指向空,

          然后就可以放心地删除13了

          正确的版本:

          

          2.该节点没有左孩子,但是有右孩子

          此时只需要把该节点的右孩子托付给父亲即可

          

          3.该节点有左孩子,不过没有右孩子

          此时只需要把该节点的左孩子托付给父亲即可

          其实第一类可以归为第二类或者第三类

          

          4.该节点既有左孩子,又有右孩子

          

          其实这里的1就是整棵树当中小于3这个值的最大值

          4就是整棵树当中大于3这个值的最小值

          他们都可以来代替3这个值

          1其实就是要删除的节点的左子树的最大值(最大值就是最右侧节点)

          4其实就是要删除的节点的右子树的最小值(最大值就是最左侧节点)

          而且1和4都有一个特点:最多只有一个孩子

          此时删除1和4就可以借助于第2种或第3种方案了

          我们今天按照寻找右子树的最小值的方式来做

          注意:之后删除3的操作不能使用递归,因为交换后就不是二叉搜索树了,就无法保证能够找到那个值了

          不过上述的讨论当中我们讨论的都是该节点有父亲的情况

          都没有讨论下面的这种情况:

          5.我要删除的是根节点呢?

          (1).根节点没有左孩子也没有右孩子

          Node* tmp = _root;
          _root=nullptr;
          delete tmp;
          

          

          (2).根节点只有1个孩子

          因为我们知道:一个二叉搜索树的左子树和右子树都是二叉搜索树

          比方说根节点只有左孩子,没有右孩子

          此时只需要让根节点等于左子树的根节点(也就是根节点的左孩子)即可

          

          删除根节点之前:

          

          删除根节点之后:

          

          可见,这么做的话,删除之后的确也还是二叉搜索树

          同理,节点只有右孩子,没有左孩子的时候

          只需要让根节点等于右子树的根节点(也就是根节点的右孩子)即可

          同理,第一种情况也可以归为第二种情况

          (3).根节点有2个孩子

          

          删除之前:

          

          删除之后:

          

          

          不过这里也分为两种情况

          1.因为查找的是右子树的最左侧节点

          也就是一路往左查找,因此最后的时候只需要让我的右孩子成为父亲的左孩子即可

          2.不过如果没有一路查找,直接找到了的话

          也就是说此时我是父亲的右孩子,那么就要让我的右孩子成为父亲的右孩子了

          上面演示的那种情况就属于第二种情况

          因此,我们就可以写出这样的代码

          里面的注释非常详细,大家如果还不是特别理解的话,

          可以对照着边走读代码边画图来更好地理解

          //删除成功,返回true
          //删除失败,说明没有这个元素,返回false
          bool Erase(const K& key)
          {
          	//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类
          	//2.有右孩子,没有左孩子
          	//3.有左孩子,没有右孩子
          	//4.有左孩子,也有右孩子
          	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
          		{
          			//1.有右孩子,没有左孩子
          			//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)
          			if (cur->_left == nullptr)
          			{
          				//要删除的是_root,且_root没有左孩子
          				//那么让右孩子变成root即可
          				if (cur == _root)
          				{
          					_root = cur->_right;
          					delete cur;
          				}
          				//说明我是父亲的左孩子
          				if (cur == parent->_left)
          				{
          					//就让我的右孩子成为父亲的左孩子
          					parent->_left = cur->_right;
          					delete cur;
          				}
          				//说明我是父亲的右孩子
          				else
          				{
          					//就让我的右孩子成为父亲的右孩子
          					parent->_right = cur->_right;
          					delete cur;
          				}
          			}
          			//2.有左孩子,没有右孩子
          			else if (cur->_right == nullptr)
          			{
          				//要删除的是_root,且_root没有左孩子
          				//那么让右孩子变成root即可
          				if (cur == _root)
          				{
          					_root = cur->_left;
          					delete cur;
          				}
          				//说明我是父亲的左孩子
          				if (cur == parent->_left)
          				{
          					//就让我的左孩子成为父亲的左孩子
          					parent->_left = cur->_left;
          					delete cur;
          				}
          				//说明我是父亲的右孩子
          				else
          				{
          					//就让我的左孩子成为父亲的右孩子
          					parent->_right = cur->_left;
          					delete cur;
          				}
          			}
          			//3.有左孩子,也有右孩子
          			//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我
          			//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点
          			//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点
          			//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了
          			else
          			{
          				parent = cur;
          				Node* MinOfRight = cur->_right;
          				while (MinOfRight->_left)
          				{
          					parent = MinOfRight;
          					MinOfRight = MinOfRight->_left;
          				}
          				//开始交换
          				swap(cur->_key, MinOfRight->_key);
          				//然后删除MinOfRight
          				//1.的确向下查找了
          				//此时MinOfRight就是parent的左孩子
          				//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了
          				if (parent->_left == MinOfRight)
          				{
          					parent->_left = MinOfRight->_right;
          					delete MinOfRight;
          				}
          				//2.没有继续往下查找
          				//此时MinOfRight就是parent的右孩子
          				//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了
          				else
          				{
          					parent->_right = MinOfRight->_right;
          					delete MinOfRight;
          				}
          			}
          			//删除成功
          			return true;
          		}
          	}
          	//此时cur为空说明没有找到
          	return false;
          }
          

          六.Find,Insert,Erase的递归版本

          1.FindR

          Find的递归版本就很简单了:

          假设要查找的值是Key

          如果当前节点的值==key:查到了,返回当前节点即可

          如果当前节点的值>key:说明当前节点值太大,往左找

          如果当前节点的值

          Node* FindR(const K& key)
          {
          	return _FindR(_root,key);
          }
          Node* _FindR(Node* root, const K& key)
          {
          	if (root == nullptr)
          	{
          		return nullptr;
          	}
          	if (root->_key > key)
          	{
          		return _FindR(root->_left, key);
          	}
          	else if(root->_key < key)
          	{
          		return _FindR(root->_right, key);
          	}
          	else
          	{
          		return root;
          	}
          }
          

          2.InsertR

          如果当前节点是空节点:说明找到了空位置,插入即可

          如果当前节点的值>key:说明当前节点值太大,往左找插入位置

          如果当前节点的值

          如果当前节点的值==key:说明重复了,返回false,不能插入重复元素

          bool InsertR(const K& key)
          {
          	return _InsertR(_root, key);
          }
          bool _InsertR(Node*& root, const K& key)
          {
          	if (root == nullptr)
          	{
          		root = new Node(key);
          		return true;
          	}
          	else if (root->_key > key)
          	{
          		return _InsertR(root->_left, key);
          	}
          	else if(root->_key < key)
          	{
          		return _InsertR(root->_right, key);
          	}
          	else
          	{
          		return false;
          	}
          }
          

          这里特别巧妙的一点在于:只要加上引用

          那么就可以不用传递父节点了

          因为root就是上一个节点的左孩子或者右孩子的别名,改变root会影响到上一个节点的左孩子或者右孩子

          这里引用作为参数的价值就显得格外巧妙了

          3.EraseR

          这里是递归版本的erase,

          而且要删除的节点跟MinOfRight交换之后,右子树是一个二叉搜索树

          因此后面删除MinOfRight的时候可以复用,直接在右子树上面删除MinOfRight即可

          而且对于删除根节点也是如此

          这里依旧使用引用作为参数,它的巧妙之处在于修改指向时特别方便了,无需传入父亲节点

          bool EraseR(const K& key)
          {
          	return _EraseR(_root, key);
          }
          bool _EraseR(Node*& root, const K& key)
          {
          	if (root == nullptr)
          	{
          		return false;
          	}
          	//1.往左找,在左子树里面删除key
          	if (root->_key > key)
          	{
          		return _EraseR(root->_left, key);
          	}
          	//2.往右找,在右子树里面删除key
          	else if (root->_key < key)
          	{
          		return _EraseR(root->_right, key);
          	}
          	// 当前的根节点
          	else
          	{
          		//root不仅仅是root,root是父亲的孩子的别名
          		//因此只需要改变root就可以改变父亲的孩子了
          		if (root->_left == nullptr)
          		{
          			//不要忘了保存root
          			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* MinOfRight = root->_right;
          			while (MinOfRight->_left)
          			{
          				MinOfRight = MinOfRight->_left;
          			}
          			swap(root->_key, MinOfRight->_key);
          			//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST
          			//所以此时递归删除root->_right上的key值即可
          			//而且也适用于直接删除根节点的情况
          			_EraseR(root->_right, key);
          		}
          	}
          	return true;
          }
          

          七.析构,拷贝构造,赋值运算符重载

          1.析构

          跟二叉树的销毁一样,后序遍历销毁

          依旧是采用递归版本

          //析构函数  后续遍历析构
          ~BSTree()
          {
          	_Destroy(_root);
          }
          void _Destroy(Node*& root)
          {
          	if (root == nullptr) return;
          	_Destroy(root->_left);
          	_Destroy(root->_right);
          	delete root;
          	root = nullptr;
          }
          

          2.拷贝构造

          先序遍历构造

          先构造根节点,然后递归构造左子树和右子树

          最后返回根节点

          //拷贝构造
          //先序遍历构造
          BSTree(const BSTree& bst)
          {
          	_root = _Copy(bst._root);
          }
          Node* _Copy(const 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;
          }
          

          3.赋值运算重载

          实现了拷贝构造之后就可以

          直接现代写法了

          //赋值运算符重载
          BSTree& operator=(BSTree bst)
          {
          	std::swap(_root, bst._root);
          	return *this;
          }
          

          八.Key模型完整代码

          template 
          struct BSTreeNode
          {
          	BSTreeNode* _left = nullptr;
          	BSTreeNode* _right = nullptr;
          	K _key;
          	BSTreeNode(const K& key)
          		:_key(key)
          	{}
          };
          template
          class BSTree
          {
          	typedef BSTreeNode Node;
          public:
          	//非递归实现insert.find,erase
          	bool Insert(const K& key)
          	{
          		if (_root == nullptr)
          		{
          			_root = new Node(key);
          			return true;
          		}
          		Node* cur = _root;
          		Node* parent = _root;//记录父亲,因为要能够插入
          		while (cur)
          		{
          			//要插入的值小于父亲,插入到左子树当中
          			if (cur->_key > key)
          			{
          				parent = cur;
          				cur = cur->_left;
          			}
          			//要插入的的值大于父亲,插入到右子树当中
          			else if (cur->_key < key)
          			{
          				parent = cur;
          				cur = cur->_right;
          			}
          			//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回false
          			else
          			{
          				return false;
          			}
          		}
          		//此时cur为空,在此位置插入value
          		cur = new Node(key);
          		//要插入的元素小于父亲,插入到左子树当中
          		if (parent->_key > key)
          		{
          			parent->_left = cur;
          		}
          		//要插入的元素大于父亲,插入到右子树当中
          		else
          		{
          			parent->_right = cur;
          		}
          		//插入成功
          		return true;
          	}
          	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 cur;
          			}
          		}
          		//此时cur为空说明没有找到
          		return nullptr;
          	}
          	bool Erase(const K& key)
          	{
          		//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类
          		//2.有右孩子,没有左孩子
          		//3.有左孩子,没有右孩子
          		//4.有左孩子,也有右孩子
          		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
          			{
          				//1.有右孩子,没有左孩子
          				//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)
          				if (cur->_left == nullptr)
          				{
          					//要删除的是_root,且_root没有左孩子
          					//那么让右孩子变成root即可
          					if (cur == _root)
          					{
          						_root = cur->_right;
          						delete cur;
          					}
          					//说明我是父亲的左孩子
          					if (cur == parent->_left)
          					{
          						//就让我的右孩子成为父亲的左孩子
          						parent->_left = cur->_right;
          						delete cur;
          					}
          					//说明我是父亲的右孩子
          					else
          					{
          						//就让我的右孩子成为父亲的右孩子
          						parent->_right = cur->_right;
          						delete cur;
          					}
          				}
          				//2.有左孩子,没有右孩子
          				else if (cur->_right == nullptr)
          				{
          					//要删除的是_root,且_root没有左孩子
          					//那么让右孩子变成root即可
          					if (cur == _root)
          					{
          						_root = cur->_left;
          						delete cur;
          					}
          					//说明我是父亲的左孩子
          					if (cur == parent->_left)
          					{
          						//就让我的左孩子成为父亲的左孩子
          						parent->_left = cur->_left;
          						delete cur;
          					}
          					//说明我是父亲的右孩子
          					else
          					{
          						//就让我的左孩子成为父亲的右孩子
          						parent->_right = cur->_left;
          						delete cur;
          					}
          				}
          				//3.有左孩子,也有右孩子
          				//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我
          				//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点
          				//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点
          				//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了
          				else
          				{
          					parent = cur;
          					Node* MinOfRight = cur->_right;
          					while (MinOfRight->_left)
          					{
          						parent = MinOfRight;
          						MinOfRight = MinOfRight->_left;
          					}
          					//开始交换
          					swap(cur->_key, MinOfRight->_key);
          					//然后删除MinOfRight
          					//1.的确向下查找了
          					//此时MinOfRight就是parent的左孩子
          					//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了
          					if (parent->_left == MinOfRight)
          					{
          						parent->_left = MinOfRight->_right;
          						delete MinOfRight;
          					}
          					//2.没有继续往下查找
          					//此时MinOfRight就是parent的右孩子
          					//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了
          					else
          					{
          						parent->_right = MinOfRight->_right;
          						delete MinOfRight;
          					}
          				}
          				//删除成功
          				return true;
          			}
          		}
          		//此时cur为空说明没有找到
          		return false;
          	}
          	//析构函数  后续遍历析构
          	~BSTree()
          	{
          		_Destroy(_root);
          	}
          	//C++11新语法
          	BSTree() = default;//强制生成默认构造
          	//拷贝构造
          	//先序遍历构造
          	BSTree(const BSTree& bst)
          	{
          		_root = _Copy(bst._root);
          	}
          	//赋值运算符重载
          	BSTree& operator=(BSTree bst)
          	{
          		std::swap(_root, bst._root);
          		return *this;
          	}
          	void InOrder()
          	{
          		_InOrder(_root);
          		cout << endl;
          	}
          	//递归实现insert.find,erase
          	Node* 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);
          	}
          private:
          	Node* _Copy(const 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;
          	}
          	void _Destroy(Node*& root)
          	{
          		if (root == nullptr) return;
          		_Destroy(root->_left);
          		_Destroy(root->_right);
          		delete root;
          		root = nullptr;
          	}
          	void _InOrder(Node* root)
          	{
          		if (root == nullptr)
          		{
          			return;
          		}
          		_InOrder(root->_left);
          		cout << root->_key << " ";
          		_InOrder(root->_right);
          	}
          	Node* _FindR(Node* root, const K& key)
          	{
          		if (root == nullptr)
          		{
          			return nullptr;
          		}
          		if (root->_key > key)
          		{
          			return _FindR(root->_left, key);
          		}
          		else if(root->_key < key)
          		{
          			return _FindR(root->_right, key);
          		}
          		else
          		{
          			return root;
          		}
          	}
          	bool _InsertR(Node*& root, const K& key)
          	{
          		if (root == nullptr)
          		{
          			root = new Node(key);
          			return true;
          		}
          		else if (root->_key > key)
          		{
          			return _InsertR(root->_left, key);
          		}
          		else if(root->_key < key)
          		{
          			return _InsertR(root->_right, key);
          		}
          		else
          		{
          			return false;
          		}
          	}
          	bool _EraseR(Node*& root, const K& key)
          	{
          		if (root == nullptr)
          		{
          			return false;
          		}
          		//1.往左找
          		if (root->_key > key)
          		{
          			return _EraseR(root->_left, key);
          		}
          		//2.往右找
          		else if (root->_key < key)
          		{
          			return _EraseR(root->_right, key);
          		}
          		// 删除
          		else
          		{
          			//root不仅仅是root,root是父亲的孩子的别名,让root成为root的右孩子即可
          			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* MinOfRight = root->_right;
          				while (MinOfRight->_left)
          				{
          					MinOfRight = MinOfRight->_left;
          				}
          				swap(root->_key, MinOfRight->_key);
          				//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST
          				//所以此时递归删除root->_right上的key值即可
          				//而且对于直接删除_root也没有任何影响
          				_EraseR(root->_right, key);
          			}
          		}
          		return true;
          	}
          	Node* _root = nullptr;
          };
          

          九.二叉搜索树的应用

          1.Key模型

          

          2.Key-Value模型

          

          下面我们把刚才Key模型的代码改为Key-Value模型

          只需要改一下:

          1.BSTreeNode节点

          2.insert

          3.InOrder的打印即可

          其他地方都不需要修改

          namespace kv
          {
          	template 
          	struct 
          	{
          		BSTreeNode* _left = nullptr;
          		BSTreeNode* _right = nullptr;
          		K _key;
          		V _value;
          		BSTreeNode(const K& key,const V& value)
          			:_key(key)
          			,_value(value)
          		{}
          	};
          	template
          	class BSTree
          	{
          		typedef BSTreeNode Node;
          	public:
          		//非递归实现insert.find,erase
          		bool Insert(const K& key,const V& value)
          		{
          			if (_root == nullptr)
          			{
          				_root = new Node(key,value);
          				return true;
          			}
          			Node* cur = _root;
          			Node* parent = _root;//记录父亲,因为要能够插入
          			while (cur)
          			{
          				//要插入的值小于父亲,插入到左子树当中
          				if (cur->_key > key)
          				{
          					parent = cur;
          					cur = cur->_left;
          				}
          				//要插入的的值大于父亲,插入到右子树当中
          				else if (cur->_key < key)
          				{
          					parent = cur;
          					cur = cur->_right;
          				}
          				//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回false
          				else
          				{
          					return false;
          				}
          			}
          			//此时cur为空,在此位置插入value
          			cur = new Node(key,value);
          			//要插入的元素小于父亲,插入到左子树当中
          			if (parent->_key > key)
          			{
          				parent->_left = cur;
          			}
          			//要插入的元素大于父亲,插入到右子树当中
          			else
          			{
          				parent->_right = cur;
          			}
          			//插入成功
          			return true;
          		}
          		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 cur;
          				}
          			}
          			//此时cur为空说明没有找到
          			return nullptr;
          		}
          		bool Erase(const K& key)
          		{
          			//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类
          			//2.有右孩子,没有左孩子
          			//3.有左孩子,没有右孩子
          			//4.有左孩子,也有右孩子
          			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
          				{
          					//1.有右孩子,没有左孩子
          					//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)
          					if (cur->_left == nullptr)
          					{
          						//要删除的是_root,且_root没有左孩子
          						//那么让右孩子变成root即可
          						if (cur == _root)
          						{
          							_root = cur->_right;
          							delete cur;
          						}
          						//说明我是父亲的左孩子
          						if (cur == parent->_left)
          						{
          							//就让我的右孩子成为父亲的左孩子
          							parent->_left = cur->_right;
          							delete cur;
          						}
          						//说明我是父亲的右孩子
          						else
          						{
          							//就让我的右孩子成为父亲的右孩子
          							parent->_right = cur->_right;
          							delete cur;
          						}
          					}
          					//2.有左孩子,没有右孩子
          					else if (cur->_right == nullptr)
          					{
          						//要删除的是_root,且_root没有左孩子
          						//那么让右孩子变成root即可
          						if (cur == _root)
          						{
          							_root = cur->_left;
          							delete cur;
          						}
          						//说明我是父亲的左孩子
          						if (cur == parent->_left)
          						{
          							//就让我的左孩子成为父亲的左孩子
          							parent->_left = cur->_left;
          							delete cur;
          						}
          						//说明我是父亲的右孩子
          						else
          						{
          							//就让我的左孩子成为父亲的右孩子
          							parent->_right = cur->_left;
          							delete cur;
          						}
          					}
          					//3.有左孩子,也有右孩子
          					//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我
          					//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点
          					//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点
          					//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了
          					else
          					{
          						parent = cur;
          						Node* MinOfRight = cur->_right;
          						while (MinOfRight->_left)
          						{
          							parent = MinOfRight;
          							MinOfRight = MinOfRight->_left;
          						}
          						//开始交换
          						swap(cur->_key, MinOfRight->_key);
          						//然后删除MinOfRight
          						//1.的确向下查找了
          						//此时MinOfRight就是parent的左孩子
          						//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了
          						if (parent->_left == MinOfRight)
          						{
          							parent->_left = MinOfRight->_right;
          							delete MinOfRight;
          						}
          						//2.没有继续往下查找
          						//此时MinOfRight就是parent的右孩子
          						//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了
          						else
          						{
          							parent->_right = MinOfRight->_right;
          							delete MinOfRight;
          						}
          					}
          					//删除成功
          					return true;
          				}
          			}
          			//此时cur为空说明没有找到
          			return false;
          		}
          		//析构函数  后续遍历析构
          		~BSTree()
          		{
          			_Destroy(_root);
          		}
          		//C++11新语法
          		BSTree() = default;//强制生成默认构造
          		//拷贝构造
          		//先序遍历构造
          		BSTree(const BSTree& bst)
          		{
          			_root = _Copy(bst._root);
          		}
          		//赋值运算符重载
          		BSTree& operator=(BSTree bst)
          		{
          			std::swap(_root, bst._root);
          			return *this;
          		}
          		void InOrder()
          		{
          			_InOrder(_root);
          			cout << endl;
          		}
          		//递归实现insert.find,erase
          		Node* FindR(const K& key)
          		{
          			return _FindR(_root, key);
          		}
          		bool InsertR(const K& key,const V& value)
          		{
          			return _InsertR(_root, key,value);
          		}
          		bool EraseR(const K& key)
          		{
          			return _EraseR(_root, key);
          		}
          	private:
          		Node* _Copy(const 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;
          		}
          		void _Destroy(Node*& root)
          		{
          			if (root == nullptr) return;
          			_Destroy(root->_left);
          			_Destroy(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* _FindR(Node* root, const K& key)
          		{
          			if (root == nullptr)
          			{
          				return nullptr;
          			}
          			if (root->_key > key)
          			{
          				return _FindR(root->_left, key);
          			}
          			else if (root->_key < key)
          			{
          				return _FindR(root->_right, key);
          			}
          			else
          			{
          				return root;
          			}
          		}
          		bool _InsertR(Node*& root, const K& key,const V& value)
          		{
          			if (root == nullptr)
          			{
          				root = new Node(key,value);
          				return true;
          			}
          			else if (root->_key > key)
          			{
          				return _InsertR(root->_left, key);
          			}
          			else if (root->_key < key)
          			{
          				return _InsertR(root->_right, key);
          			}
          			else
          			{
          				return false;
          			}
          		}
          		bool _EraseR(Node*& root, const K& key)
          		{
          			if (root == nullptr)
          			{
          				return false;
          			}
          			//1.往左找
          			if (root->_key > key)
          			{
          				return _EraseR(root->_left, key);
          			}
          			//2.往右找
          			else if (root->_key < key)
          			{
          				return _EraseR(root->_right, key);
          			}
          			// 删除
          			else
          			{
          				//root不仅仅是root,root是父亲的孩子的别名,让root成为root的右孩子即可
          				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* MinOfRight = root->_right;
          					while (MinOfRight->_left)
          					{
          						MinOfRight = MinOfRight->_left;
          					}
          					swap(root->_key, MinOfRight->_key);
          					//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST
          					//所以此时递归删除root->_right上的key值即可
          					//而且对于直接删除_root也没有任何影响
          					_EraseR(root->_right, key);
          				}
          			}
          			return true;
          		}
          		Node* _root = nullptr;
          	};
          }
          

          下面我们来测试一下

          一个是统计单词出现的次数

          一个是英汉互译的词典

          void TestBSTree()
          {
          	string strs[] = { "apple","Banana","Grape","Mango","apple","Banana" ,"apple","Mango" ,"Mango" ,"Mango" ,"Mango" };
          	// 统计单词出现的次数
          	kv::BSTree countTree;
          	for (auto str : strs)
          	{
          		auto ret = countTree.Find(str);
          		if (ret == NULL)
          		{
          			countTree.Insert(str, 1);
          		}
          		else
          		{
          			ret->_value++;
          		}
          	}
          	countTree.InOrder();
          	//英汉互译的词典
          	kv::BSTree dict;
          	dict.Insert("insert", "插入");
          	dict.Insert("erase", "删除");
          	dict.Insert("BST", "二叉搜索树");
          	dict.Insert("KV", "key-value模型");
          	string str;
          	while (cin >> str)
          	{
          		auto ret = dict.Find(str);
          		if (ret)
          		{
          			cout << str << ":" << ret->_value << endl;
          		}
          		else
          		{
          			cout << "单词拼写错误" << endl;
          		}
          	}
          }
          

          

          以上就是C++ 二叉搜索树(BST)的实现(非递归版本与递归版本)与应用的全部内容,希望能对大家有所帮助!