【C++】二叉搜索树（概念、操作）

07-16 717阅读

🌈个人主页：秦jh_-CSDN博客
🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

前言

二叉搜索树

概念

操作

查找

插入

中序遍历

编辑

删除

二叉搜索树的应用

性能分析

前言

💬 hello! 各位铁子们大家好哇。

今日更新了二叉搜索树的相关内容

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

二叉搜索树

概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

操作

查找

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

插入

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点。默认不能冗余，如果已经有相同的值了，就插入失败。

中序遍历

二叉搜索树的中序遍历，其实就是升序后的排序。因为根节点是私有的，这里不适合用友元。所以对于递归的函数，可以弄一个子函数为私有，套一层在外面，这里就不需要传形参了，不需要访问私有的根节点了。

删除

上图是我们即将使用的搜索二叉树模型。

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

要删除的结点无孩子结点（情况1）
要删除的结点只有左孩子结点（情况2）
要删除的结点只有右孩子结点（情况3）
要删除的结点有左、右孩子结点（情况4）

实际上，情况1可以和2，3合并起来，不需要额外判断。

实际删除过程：

情况2：删除该节点且使该节点的父节点指向该节点的左孩子。
情况3：删除该节点且使该节点的父节点指向该节点的右孩子。

情况4：在它的右子树找最左节点进行交换，然后再处理该节点的删除问题。（或者找左子树的最右节点进行替换）

删除的完整代码：

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key _right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//删除
				//左为空，父亲指向我的右
				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
				{
					//左右都不为空，替换法删除
					//查找右子树的最左节点替代删除（也可找左子树的最右节点替换）
                    //注意删除根节点的特殊情况，此时rightmin的父亲为cur
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					swap(cur->_key, rightMin->_key);
                    
                    //判断rightmin在父亲的左边还是右边
                    //rightmin左边为空，所以rightmin的父亲指向rightmin的右边
					if(rightMinParent->_left==rightMin)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;
					delete rightMin;
				}
				return true;
			}
		}
		return false;
	}

注意，当删除全部节点时，需要更新根节点，如上图。

二叉搜索树的应用

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

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

K模型代码：

namespace key
{
	template
	struct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;
		K _key;
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};
	template
	class BSTree
	{
		typedef BSTreeNode Node;
	public:
		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key _right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key);
			if (parent->_key > key)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			return true;
		}
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key _right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key _right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//删除
					//左为空，父亲指向我的右
					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* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}
						swap(cur->_key, rightMin->_key);
						if (rightMinParent->_left == rightMin)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;
						delete rightMin;
					}
					return true;
				}
			}
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout _left);
			cout _key _key _right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key,val);
			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 _right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key _right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//删除
					//左为空，父亲指向我的右
					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* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}
						swap(cur->_key, rightMin->_key);
						if (rightMinParent->_left == rightMin)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;
						delete rightMin;
					}
					return true;
				}
			}
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout _left);
			cout _key _right);
		}
	private:
		Node* _root = nullptr;
	};
	void BSTreeTest2()
	{
		BSTree dict;
		dict.Insert("string", "字符串");
		dict.Insert("left", "左边");
		dict.Insert("insert", "插入");
		string str;
		while (cin >> str)
		{
			BSTreeNode* ret = dict.Find(str);
			if (ret)
			{
				cout _val

VPS购买请点击我

【C++】二叉搜索树（概念、操作）

前言

二叉搜索树

概念

操作

查找

插入

中序遍历

删除

二叉搜索树的应用

相关阅读

aspx怎么对接支付接口?

一粒挺怎么吃?

齐博怎么样?

海哲蜇伤怎么办?

目录[+]

前言

二叉搜索树

概念

操作

查找

插入

中序遍历

​

删除

二叉搜索树的应用

相关阅读

aspx怎么对接支付接口?

一粒挺怎么吃?

齐博怎么样?

海哲蜇伤怎么办?

目录[+]