
template<class T>
struct BSTNode
{
 BSTNode(const T& data = T())
   : _pLeft(nullptr) , _pRight(nullptr), _data(data)
 {}
 BSTNode<T>* _pLeft;
 BSTNode<T>* _pRight;
 T _data;
};
template<class T>
class BSTree
{
 typedef BSTNode<T> Node;
 typedef Node* PNode;
public:
 BSTree(): _pRoot(nullptr)
 {}
 // 自己实现，与二叉树的销毁类似
 ~BSTree();
 // 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置
 PNode Find(const T& data);
 bool Insert(const T& data)
 {
 // 如果树为空，直接插入
 if (nullptr == _pRoot)
 {
 _pRoot = new Node(data);
 return true;
 }
 // 按照二叉搜索树的性质查找data在树中的插入位置
 PNode pCur = _pRoot;
 // 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置
 PNode pParent = nullptr;
 while (pCur)
 {
 pParent = pCur;
 if (data < pCur->_data)
比特就业课
 pCur = pCur->_pLeft;
 else if (data > pCur->_data)
 pCur = pCur->_pRight;  // 元素已经在树中存在
 else
 return false;
 }
 // 插入元素
 pCur = new Node(data);
 if (data < pParent->_data)
 pParent->_pLeft = pCur;
 else
 pParent->_pRight = pCur;
 return true;
 }
 bool Erase(const T& data)
 {
 // 如果树为空，删除失败
 if (nullptr == _pRoot)
 return false;
 // 查找在data在树中的位置
 PNode pCur = _pRoot;
 PNode pParent = nullptr;
 while (pCur)
 {
 if (data == pCur->_data)
 break;
 else if (data < pCur->_data)
 {
 pParent = pCur;
 pCur = pCur->_pLeft;
 }
 else
 {
 pParent = pCur;
 pCur = pCur->_pRight;
 }
 }
 // data不在二叉搜索树中，无法删除
 if (nullptr == pCur)
 return false;
 // 分以下情况进行删除，同学们自己画图分析完成
 if (nullptr == pCur->_pRight)
 {
 // 当前节点只有左孩子或者左孩子为空---可直接删除
 }
 else if (nullptr == pCur->_pRight)
 {
 // 当前节点只有右孩子---可直接删除
 }
 else
 {
// 当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，
比如：
 // 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节
点，即右子树中最小的节点
 // 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
 }
 return true;
 }
// 自己实现
 void InOrder();
private:
 PNode _pRoot;
};

四、二叉搜索树的应用

在我们目前的学习中，二叉搜索树最重要的用途就是key--val模型，KV模型就是每一个key值都对应一个val值，这样就形成一个<key,val>键值对，这样的应用在生活中是非常常见的

比如：在菜市场中不同的蔬菜对应着不同的价格；新华词典中，不同的汉字对应着不同的拼音，这些都可以用KV模型来解决

下面是KV模型的实现（没有主函数）：


namespace kv
{
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
 
		BSTreeNode(const K& key,const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};
 
	template<class K,class V>
	class BSTree
	{
		typedef BSTreeNode<K,V> Node;
	public:
		//遍历（中序）
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
		///
		bool Insert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}
 
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;
 
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
 
			cur = new Node(key,value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
 
			return true;
		}
 
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
 
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 准备删除  20:15继续
					if (cur->_left == nullptr)
					{//左为空
						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)
					{//右为空
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
 
						delete cur;
					}
					else
					{//左右都不为空
 
						// 右树的最小节点(最左节点)
						Node* parent = cur;
						Node* subLeft = cur->_right;
						while (subLeft->_left)
						{
							parent = subLeft;
							subLeft = subLeft->_left;
						}
 
						swap(cur->_key, subLeft->_key);
 
						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
 
						delete subLeft;
					}
					return true;
				}
			}
 
			return false;
		}
 
		BSTree() = default;
		~BSTree()
		{
			Destroy(_root);
		}
 
		//递归版本
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
 
		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
 
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
		BSTree(const BSTree<K,V>& t)
		{
			_root = Copy(t._root);
		}
		BSTree<K,V>& operator=(BSTree<K,V> t)
		{
			swap(_root, t._root);
			return *this;
		}
	private:
		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;
		}
		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
		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)
				{
					root = root->_right;
					return true;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
					return true;
				}
				else
				{
					Node* subLeft = root->_right;
					while (subLeft->_left)
					{
						subLeft = subLeft->_left;
					}
					swap(root->_key, subLeft->_key);
					return _EraseR(root->_right, key);
				}
			}
		}
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
			{
				return root->_right;
			}
			else if (root->_key > key)
			{
				return root->_left;
			}
			else
			{
				return true;
			}
		}
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}
		Node* _root = nullptr;
	};
}

五、总结

以上就是二叉搜索树的主要内容，在代码实现上其实与之前讲的二叉树差别并不是很大，关键在于思路的梳理，这章就先到这了

感谢各位大佬观看，创作不易，还请各位大佬点赞支持！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/893099