首页 > 其他分享 >二叉搜索树

二叉搜索树

时间：2023-10-28 23:02:01浏览次数：27  
标签：return cur 二叉 搜索 key root 节点 left

一、二叉搜索树的概念

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

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

二叉搜索树_递归

二、二叉搜索树的实现

1、基本结构

template<class K>
struct BSTNode//节点
{
	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
	K _key;//数据
	BSTNode<K>* _left;//左指针
	BSTNode<K>* _right;//右指针
};
template<class K>
class BSTree//二叉搜索数树
{
public:
	typedef BSTNode<K> Node;
protected:
	Node* _root = nullptr;//根节点
};

2、Insert函数

  • 如果树为空，直接新增节点，赋值给root指针
  • 树不为空，按二叉搜索树的性质查找插入位置，插入新节点
  • 注意，二叉搜索树是不允许重复值的，如果有重复值，返回false
bool Insert(const K& key)
{
	if (_root == nullptr)//如果此时树为空
	{
		_root = new Node(key);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr)//开始寻找插入的地方
	{
		parent = cur;
		if (cur->_key < key)//如果当前节点的key小于要插入节点的key
		{
			cur = cur->_right;//往右边走
		}
		else if (cur->_key > key)//如果当前节点的key大于要插入节点的key
		{
			cur = cur->_left;//往左边走
		}
		else//如果当前节点的key等于要插入节点的key
		{
			return false;
		}
	}
	//退出来后虽然已经找到了要插入的位置，但是需要判断插入到左边还是右边
	if (parent->_key < key)
	{
		parent->_right = new Node(key);//插入到右边
	}
  else if (parent->_key > key)
	{
		parent->_left = new Node(key);//插入到左边
	}
	return true;
}

3、InOrder函数

如果用中序遍历二叉搜索树，得出的结果是有序的。

void _Inorder(Node* root)//子函数
{
	if (root == nullptr)
	{
		return;
	}
	_Inorder(root->_left);
	cout << root->_key << " ";
	_Inorder(root->_right);
}
void Inorder()//中序遍历
{
	_Inorder(_root);
	cout << endl;
}

4、Find函数

  • 从根节点开始查找，进行比较，比当前节点大则往右边查找，比当前节点小则王左边查找
  • 最多查找树的高度次，走到空还没找到，这个值不存在。
bool Find(const K& key)
{
	Node* cur = _root;
	//按照二叉树的性质来找
	while (cur)
	{
		if (cur->_key < key)//当前节点小于key
		{
			cur = cur->_right;//往右走
		}
		else if(cur->_key > key)//当前节点大于key
		{
			cur = cur->_left;//往左走
		}
		else
		{
			return true;//找到了
		}
	}
	return false;//没找到
}

5、Erase函数

首先得查找要删除的元素是否在树中，如果不存在，则返回false，否则就进行删除，在删除节点时，可能会遇到以下几种情况

a.要删除节点无孩子节点

b.要删除的节点只有左孩子节点

c.要删除的节点只有右孩子节点

d.要删除的节点有左、右孩子节点

在实际情况中，情况a可以和情况b或者c合并起来，因此真正的删除过程如下：

  • 情况b：删除该节点，并且让被删除节点的父节点指向被删除节点的左孩子节点。

二叉搜索树_递归_02

  • 情况c：删除该节点，并且让被删除节点的父节点指向被删除节点的右孩子节点。

二叉搜索树_二叉搜索树_03

  • 情况d：在它的右子树中寻找最小的节点，用最小节点的值替换被删除的节点的值，最后删除最小节点。

二叉搜索树_递归_04

bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr)//查找要删除的节点
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		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;
				return true;
			}
			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;
				return true;
			}
			else////如果要删除的节点有左孩子节点也有右孩子节点
			{
				parent = cur;
				Node* MinLeft = cur->_right;
				while (MinLeft->_left != nullptr)//找到右边最小的节点
				{
					parent = MinLeft;
					MinLeft = MinLeft->_left;
				}
				swap(cur->_key, MinLeft->_key);//交换
				//删除右边交换过去的节点
        //被删除的节点右边可能右孩子节点，用它的父节点连接
				if (parent->_left == MinLeft)//用父节点的左指针连接
				{
					parent->_left = MinLeft->_right;
				}
				else//用父节点的右指针连接
				{
					parent->_right = MinLeft->_right;
				}
				delete MinLeft;
				return true;
			}
		}
	}
	return false;//没有这个key，删除失败
}

6、递归实现Find函数

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 if (root->_key == key)
	{
		return true;
	}
}
bool FindR(const K& key)//递归实现查找
{
	return _FindR(_root, key);
}

7、递归实现Insert函数

bool _InsertR(Node*& root, const K& key)//递归插入子函数
{
	if (root == nullptr)//找到插入的位置
	{
		//注意，这里的root传的是引用，所以可以直接指向新节点
		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;
	}
}
bool InsertR(const K& key)//递归实现插入
{
	return _InsertR(_root, key);
 }

8、递归实现Erase函数

bool _EraseR(Node*& root, const K& key)//递归删除子函数
{
	//root传引用
	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->_right == nullptr)//只有左孩子节点
		{
			Node* del = root;//记录要删除的节点
			root = root->_left;//指向被删除的节点的左孩子节点
			delete del;
			return true;
		}
		else if (root->_left == nullptr)//只有右孩子节点
		{
			Node* del = root;//记录要删除的节点
			root = root->_right;//指向被删除的节点的右孩子节点
			delete del;
			return true;
		}
		else//右左孩子节点也有右孩子节点
		{
			Node* MinLeft = root->_right;
			while (MinLeft->_left != nullptr)//找右子树的最小节点
			{
				MinLeft = MinLeft->_left;
			}
			swap(root->_key, MinLeft->_key);//交换
			_EraseR(root->_right, key);//继续递归删除交换后的节点
		}
	}
	return false;
}	
bool EraseR(const K& key)//递归删除
{
		return _EraseR(_root, key);
}

9、析构函数

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

10、拷贝构造函数与赋值重载函数

Node* Copy(Node* root)//拷贝子函数
{
	if (root == nullptr)
	{
		return nullptr;
	}
	Node* newNode = new Node(root->_key);
	newNode->_left = Copy(root->_left);
	newNode->_right = Copy(root->_right);
	return newNode;
}
BSTree(const BSTree<K>& t)//拷贝构造
{
	_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)//赋值重载
{
	swap(_root, t._root);
	return *this;
}

11、全部代码

template<class K>
struct BSTNode//节点
{
	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}

	K _key;//数据
	BSTNode<K>* _left;//左指针
	BSTNode<K>* _right;//右指针
};
template<class K>
class BSTree//二叉搜索数树
{
public:
	typedef BSTNode<K> Node;
	BSTree() = default;//默认构造函数
	BSTree(const BSTree<K>& t)//拷贝构造
	{
		_root = Copy(t._root);
	}
	~BSTree()//析构函数
	{
		Destroy(_root);
	}
	BSTree<K>& operator=(BSTree<K> t)//赋值重载
	{
		swap(_root, t._root);
		return *this;
	}

	Node* a()
	{
		return _root;
	}
	bool Insert(const K& key)
	{
		if (_root == nullptr)//如果此时树为空
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)//开始寻找插入的地方
		{
			parent = cur;
			if (cur->_key < key)//如果当前节点的key小于要插入节点的key
			{
				cur = cur->_right;//往右边走
			}
			else if (cur->_key > key)//如果当前节点的key大于要插入节点的key
			{
				cur = cur->_left;//往左边走
			}
			else//如果当前节点的key等于要插入节点的key
			{
				return false;
			}
		}
		//退出来后虽然已经找到了要插入的位置，但是需要判断插入到左边还是右边
		if (parent->_key < key)
		{
			parent->_right = new Node(key);//插入到右边
		}
		else if (parent->_key > key)
		{
			parent->_left = new Node(key);//插入到左边
		}
		return true;
	}
	void Inorder()//中序遍历
	{
		_Inorder(_root);
		cout << endl;
	}
	bool Find(const K& key)
	{
		Node* cur = _root;
		//按照二叉树的性质来找
		while (cur)
		{
			if (cur->_key < key)//当前节点小于key
			{
				cur = cur->_right;//往右走
			}
			else if(cur->_key > key)//当前节点大于key
			{
				cur = cur->_left;//往左走
			}
			else
			{
				return true;//找到了
			}
		}
		return false;//没找到
	}
	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)//查找要删除的节点
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			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;
					return true;
				}
				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;
					return true;
				}
				else////如果要删除的节点有左孩子节点也有右孩子节点
				{
					parent = cur;
					Node* MinLeft = cur->_right;
					while (MinLeft->_left != nullptr)//找到右边最小的节点
					{
						parent = MinLeft;
						MinLeft = MinLeft->_left;
					}
					swap(cur->_key, MinLeft->_key);//交换
					//删除右边交换过去的节点
					if (parent->_left == MinLeft)
					{
						parent->_left = MinLeft->_right;
					}
					else
					{
						parent->_right = MinLeft->_right;
					}
					delete MinLeft;
					return true;
				}
			}
		}
		return false;//没有这个key，删除失败
	}
	bool FindR(const K& key)//递归实现查找
	{
		return _FindR(_root, key);
	}
	bool _InsertR(Node*& root, const K& key)//递归插入子函数
	{
		if (root == nullptr)//找到插入的位置
		{
			//注意，这里的root传的是引用，所以可以直接指向新节点
			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;
		}
	}
	bool InsertR(const K& key)//递归实现插入
	{
		return _InsertR(_root, key);
	}
	bool EraseR(const K& key)//递归删除
	{
		return _EraseR(_root, key);
	}
protected:
	void _Inorder(Node* root)//中序遍历子函数
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}
	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 if (root->_key == key)
		{
			return true;
		}
	}
	bool _EraseR(Node*& root, const K& key)//递归删除子函数
	{
		//root传引用
		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->_right == nullptr)//只有左孩子节点
			{
				Node* del = root;//记录要删除的节点
				root = root->_left;//指向被删除的节点的左孩子节点
				delete del;
				return true;
			}
			else if (root->_left == nullptr)//只有右孩子节点
			{
				Node* del = root;//记录要删除的节点
				root = root->_right;//指向被删除的节点的右孩子节点
				delete del;
				return true;
			}
			else//右左孩子节点也有右孩子节点
			{
				Node* MinLeft = root->_right;
				while (MinLeft->_left != nullptr)//找右子树的最小节点
				{
					MinLeft = MinLeft->_left;
				}
				swap(root->_key, MinLeft->_key);//交换
				_EraseR(root->_right, key);//继续递归删除交换后的节点
			}
		}
		return false;
	}
	void Destroy(Node*& root)//析构子函数
	{
		//用后序遍历
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
	Node* Copy(Node* root)//拷贝子函数
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* newNode = new Node(root->_key);
		newNode->_left = Copy(root->_left);
		newNode->_right = Copy(root->_right);
		return newNode;
	}
	Node* _root = nullptr; //根节点
};

三、二叉搜索树的应用

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

比如：给一个单词world，判断该单词是否拼写正确，具体方式如下：

  • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

2、KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方

式在现实生活中非常常见：

  • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
  • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出



完结。。。。。

标签：return,cur,二叉,搜索,key,root,节点,left
From： https://blog.51cto.com/u_15855358/8073096

相关文章

  • 04-搜索技能
    目录一.限定关键词:"xxxx"二.选定标题关键词:intitle:xxxx一.限定关键词:"xxxx"关键词加双引号,会准确搜索这个词,类似全词匹配.例如:"2023年全球人口数量"二.选定标题关键词:intitle:xxxx在关键词前面加intitle:那么搜索结果中的标题就会带有该关键词.......
  • 代码随想训练营第十六天（Pyhton）｜ 104.二叉树的最大深度、 111.二叉树的最小深度、222.完
    104.二叉树的最大深度1、后续遍历递归法classSolution:defmaxDepth(self,root:Optional[TreeNode])->int:ifrootisNone:return0left_depth=self.maxDepth(root.left)#左right_depth=self.maxDepth(root.right)#......
  • linux解压缩，复制，重命名，删除，目录按更新时间排序，grep递归搜索文档
    linux解压缩，复制，重命名，删除，目录按更新时间排序，grep递归搜索文档1.解压缩压缩命令zip-p-rmymail-1026.zipmymail/解压命令unzipmymail-1026.zip2.复制将文件file1复制到dir1目录下的file2文件cpfile1dir1/file2将文件夹source_dir复制到target_dir目前并且修改......
  • 释放搜索潜力：基于ES(ElasticSearch)打造高效的语义搜索系统，让信息尽在掌握
    释放搜索潜力：基于ES(ElasticSearch)打造高效的语义搜索系统，让信息尽在掌握[1.安装部署篇--简洁版]，支持Linux/Windows部署安装效果展示PaddleNLPPipelines是一个端到端智能文本产线框架，面向NLP全场景为用户提供低门槛构建强大产品级系统的能力。本项目将通过一种简单高效的......
  • 释放搜索潜力：基于ES(ElasticSearch)打造高效的语义搜索系统，让信息尽在掌握
    释放搜索潜力：基于ES(ElasticSearch)打造高效的语义搜索系统，让信息尽在掌握[1.安装部署篇--简洁版]，支持Linux/Windows部署安装效果展示PaddleNLPPipelines是一个端到端智能文本产线框架，面向NLP全场景为用户提供低门槛构建强大产品级系统的能力。本项目将通过一种简单高效的......
  • C++从std::vector<int>类型数据创建二叉树
    背景在和chatGPT的日常代码交流中，这位“老师”总能给出不不少好代码，以下就是C++从std::vector类型数据创建二叉树的完整代码段：TreeNode*createBinaryTree(conststd::vector<int>&nodes,intindex){if(index>=nodes.size()||nodes[index]==-1){retu......
  • [Leetcode] 0104. 二叉树的最大深度
    104.二叉树的最大深度题目描述给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树[3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度 3。......
  • leetcode98-验证二叉搜索树
    一开始没有考虑到左子树的所有节点都要小于根节点，右子树要大于根节点，本质上是边界没有考虑仔细，所以比较时需向上比较（和父节点）而不是向下比较（和子节点比大小）根节点没有父节点，因此初始化时引用最大最小值即可，注意这里的数值范围点击查看代码classSolution{publicboolean......
  • 94.二叉树的中序遍历
    1.题目介绍给定一个二叉树的根节点root，返回它的中序遍历。示例1：输入：root=[1,null,2,3]输出：[1,3,2]示例2：输入：root=[]输出：[]示例3：输入：root=[1]输出：[1]提示：树中节点数目在范围[0,100]内-100<=Node.val<=1002.题解2.1递归首先我们需......
  • 信息搜索：全文搜索功能是网站运营的助力点
    产品界面通常采用高信息密度和高交互密度的设计，这是为了满足用户对多功能和复杂业务的需求。为了使用户能够快速获取所需信息并完成任务，产品中广泛使用各种搜索功能，无论大小都会有搜索功能，以提高用户的信息获取和消费效率。而全文搜索是搜索功能中体验更好的一种模式。全文搜索功能......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99