二叉搜索树的模拟实现

节点结构

分为左指针，右指针和数据域

除此之外我们还需要进一步写一个构造函数，让新生成的节点可以使用，要进行初始化，比如指针置空和数据的拷贝，为了其多样性我们应该要用模板。

template <class K>
struct BSTNode
{
	K  _key;
	BSTNode<K>* _left;
	BSTNode<K> * _right;

	//构造函数
	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};

树的结构

运用原来的节点，避免忘记传入类型，将根节点置空。

insert插入操作

在执行插入操作的时候，cue直接new一个，没办法与上面的parent节点产生链接，也就是说，有parent但是找不到cur的位置，所以我们要记录cur的父亲节点。

bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	//可以用递归也可以不用
	Node* cur= _root;
	Node* parent = nullptr;

	while (cur!=nullptr)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//tree是否可以插入相同的值
		else return false;
	}
	cur = new Node(key);
	if (cur->_key < parent->_key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	return true;
}

中序遍历（非递归实现）

到实践的时候，发现传参很不方便，因为节点是私有的，在类外不能进行访问

可以采用下面方法

private中序遍历的子函数，用public函数调用private子函数就可以完成实现

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

	}

find

与插入的逻辑很相似，在insert函数稍加修改即可

bool find (const K& key)
{
	Node* cur = _root;
	while (cur != nullptr)
	{
		if (cur->_key < key)
		{
			
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			
			cur = cur->_left;
		}
		else
		{
			  //cout << "找到了" << key << endl;
			return true;
		}
	}
	//cout << "没找到" << endl;
	return false;
}

erase

删除操作是里面最难的操作要分析多个条件

1.删除的是叶子节点或者是只有一个孩子的节点相对而言较为简单，将节点删除，parent节点left或者right置nullptr，有一个孩子的需要将他的parent连接到该节点的孩子

2.接下来是相对麻烦的，删除的节点同时拥有左孩子和右孩子。想要让左孩子的最大值或者有孩子的最小值来代替这个节点

第二种的情况更加复杂

如果以上面的方法来做，这种情况可以解决。

但是对于这种情况就会失效

要注意根的位置

这样对上面情况的分析也是要考虑根的情况，不然会有空指针的解引用问题

//删除
bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	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->_left == nullptr && cur->_right == nullptr)
			 {
				 if (cur != _root)
				 {
					 //左右孩子都为空时
					 if (parent->_key > cur->_key)
						 parent->_left = nullptr;
					 else
						 parent->_right = nullptr;
					 delete cur;
					 return true;
				 }
				 else
				 {
					 delete cur;
				 }

			}
			 
			 else if (cur->_left == nullptr)
			 {
					 if (cur != _root)
					 {
				
					 //cur只有右孩子
					 if (parent->_left == cur)
						 parent->_left = cur->_right;
					 else
						 parent->_right = cur->_right;
					 delete cur;
					 return true;
					 }
					 else
					 {
						 _root = cur->_right;
					 }

			 }
			 
			 
			else if (cur->_right == nullptr)
			{
					 if (cur != _root)
					 {
					 //cur只有左孩子
					 if (parent->_left == cur)
						 parent->_left = cur->_left;
					 else
						 parent->_right = cur->_left;
					 delete cur;
					 return true;
					 }

					 else
					 {
						 _root = cur->_left;
					 }
			 }
			
			 else
			 {
				 //cur既有左孩子又有右孩子
				 //target找到左孩子最大，或者右孩子的最小,这里我们选择找左孩子最大
				 //cur和target的key交换，删除target的节点，target的parent节点置空。
				 Node* maxleft = cur->_left;
				 Node* maxleftparent = cur;

				 while (maxleft->_right != nullptr)
				 {
					 maxleftparent = maxleft;
					 maxleft = maxleft->_right;

				 }
					 cur->_key = maxleft->_key;
					 if(maxleft==maxleftparent->_left)
					 {
						 maxleftparent->_left = maxleft->_left;
					 }
					 else
					 {
						 maxleftparent->_right = maxleft->_left;
					 }
					 delete maxleft;
			 }
			
		}
	}
	return false;
}

插入insert（递归实现）

与非递归实现相类似也是需要解决传参不方便的问题。

与非递归不同，参数还要多传入一个节点，

先一直递归，然后找到插入的位置，new一个节点给root

走到最后递归出口是root为nullptr

但是问题是如何能让root，new一个新的节点的时候与之前的父亲节点产生联系。

重点就是在于引用，让root的引用可以引起全局的变化，就和传值返回和传址返回的区别一样。

	void insert(const K& key)
	{
		_insert(_root,key);
		
	}
private:
	bool _insert(Node* root,const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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


#pragma once
#include<iostream>
using namespace std;
 
template <class K>
struct BSTNode
{
	K  _key;
	BSTNode<K>* _left;
	BSTNode<K> * _right;

	//构造函数
	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};


template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		//可以用递归也可以不用
		Node* cur= _root;
		Node* parent = nullptr;

		while (cur!=nullptr)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			//tree是否可以插入相同的值
			else return false;
		}
		cur = new Node(key);
		if (cur->_key < parent->_key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}


	
	
	//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		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->_left == nullptr && cur->_right == nullptr)
				 {
					 if (cur != _root)
					 {
						 //左右孩子都为空时
						 if (parent->_key > cur->_key)
							 parent->_left = nullptr;
						 else
							 parent->_right = nullptr;
						 delete cur;
						 return true;
					 }
					 else
					 {
						 delete cur;
					 }

				}
				 
				 else if (cur->_left == nullptr)
				 {
						 if (cur != _root)
						 {
					
						 //cur只有右孩子
						 if (parent->_left == cur)
							 parent->_left = cur->_right;
						 else
							 parent->_right = cur->_right;
						 delete cur;
						 return true;
						 }
						 else
						 {
							 _root = cur->_right;
						 }

				 }
				 
				 
				else if (cur->_right == nullptr)
				{
						 if (cur != _root)
						 {
						 //cur只有左孩子
						 if (parent->_left == cur)
							 parent->_left = cur->_left;
						 else
							 parent->_right = cur->_left;
						 delete cur;
						 return true;
						 }

						 else
						 {
							 _root = cur->_left;
						 }
				 }
				
				 else
				 {
					 //cur既有左孩子又有右孩子
					 //target找到左孩子最大，或者右孩子的最小,这里我们选择找左孩子最大
					 //cur和target的key交换，删除target的节点，target的parent节点置空。
					 Node* maxleft = cur->_left;
					 Node* maxleftparent = cur;

					 while (maxleft->_right != nullptr)
					 {
						 maxleftparent = maxleft;
						 maxleft = maxleft->_right;

					 }
						 cur->_key = maxleft->_key;
						 if(maxleft==maxleftparent->_left)
						 {
							 maxleftparent->_left = maxleft->_left;
						 }
						 else
						 {
							 maxleftparent->_right = maxleft->_left;
						 }
						 delete maxleft;
				 }
				
			}
		}
		return false;
	}
	bool find (const K& key)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < key)
			{
				
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				
				cur = cur->_left;
			}
			else
			{
				  //cout << "找到了" << key << endl;
				return true;
			}
		}
		//cout << "没找到" << endl;
		return false;
	}
	//中序遍历
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	void insert(const K& key)
	{
		_insert(_root,key);
		
	}
private:
	bool _insert(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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



	
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);

	}
private:
	Node* _root=nullptr;
};

二叉搜索树的应用

1.只有key作为关键码<set>，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。比如小区车库识别，然后抬杆的操作，还有检查单词是否拼写错误。
2.每一个关键码key<map>，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。比如看一个词在文章里面的出现次数，翻译词典中英互译。

key/value二叉搜索树代码实现

这个修改相对比较简单，多添加一个模板参数

然后在节点，和树那里修改，new一个节点也要加

对find稍加修改

#pragma once
#include<iostream>
using namespace std;
 
template <class K,class V>
struct BSTNode
{
	K  _key;
	V  _value;
	BSTNode<K,V>* _left;
	BSTNode<K,V> * _right;

	//构造函数
	BSTNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};


template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
public:
	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!=nullptr)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			//tree是否可以插入相同的值
			else return false;
		}
		cur = new Node(key,value);
		if (cur->_key < parent->_key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}


	
	
	//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		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->_left == nullptr && cur->_right == nullptr)
				 {
					 if (cur != _root)
					 {
						 //左右孩子都为空时
						 if (parent->_key > cur->_key)
							 parent->_left = nullptr;
						 else
							 parent->_right = nullptr;
						 delete cur;
						 return true;
					 }
					 else
					 {
						 delete cur;
					 }

				}
				 
				 else if (cur->_left == nullptr)
				 {
						 if (cur != _root)
						 {
					
						 //cur只有右孩子
						 if (parent->_left == cur)
							 parent->_left = cur->_right;
						 else
							 parent->_right = cur->_right;
						 delete cur;
						 return true;
						 }
						 else
						 {
							 _root = cur->_right;
						 }

				 }
				 
				 
				else if (cur->_right == nullptr)
				{
						 if (cur != _root)
						 {
						 //cur只有左孩子
						 if (parent->_left == cur)
							 parent->_left = cur->_left;
						 else
							 parent->_right = cur->_left;
						 delete cur;
						 return true;
						 }

						 else
						 {
							 _root = cur->_left;
						 }
				 }
				
				 else
				 {
					 //cur既有左孩子又有右孩子
					 //target找到左孩子最大，或者右孩子的最小,这里我们选择找左孩子最大
					 //cur和target的key交换，删除target的节点，target的parent节点置空。
					 Node* maxleft = cur->_left;
					 Node* maxleftparent = cur;

					 while (maxleft->_right != nullptr)
					 {
						 maxleftparent = maxleft;
						 maxleft = maxleft->_right;

					 }
						 cur->_key = maxleft->_key;
						 if(maxleft==maxleftparent->_left)
						 {
							 maxleftparent->_left = maxleft->_left;
						 }
						 else
						 {
							 maxleftparent->_right = maxleft->_left;
						 }
						 delete maxleft;
				 }
				
			}
		}
		return false;
	}
	Node* find (const K& key)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < key)
			{
				
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				
				cur = cur->_left;
			}
			else
			{
				  //cout << "找到了" << key << endl;
				return cur;
			}
		}
		//cout << "没找到" << endl;
		return nullptr;
	}
	//中序遍历
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	/*void insert(const K& key)
	{
		_insert(_root,key);
		
	}*/
private:
	/*bool _insert(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key < key)
			return _insert(root->_right, key);
		else if (root->_key > key)
			return _insert(root->_left, key);
		else
			return false;
	}*/



	
	void _Inorder(Node* root)
{
	if (root == nullptr)
		return;
	_Inorder(root->_left);
	cout << root->_key << " " << root->_value << endl;;
	_Inorder(root->_right);

}
private:
	Node* _root=nullptr;
};

至此二叉搜索树的模拟实践到此结束

# c++ # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

人工智能训练师-职业发展规划与持续学习

avatar 亚马逊云科技技术品牌专区

AIGC（生成式AI）试用 53 -- 个人知识库 DocsGpt(Agent)

AIGC（生成式AI）试用 53 -- 个人知识库 DocsGpt(Agent)

avatar 亚马逊云科技技术品牌专区
cover

【硬件+APP+云平台】30.1.智能仓储-V2.0-基于STM32嵌入式物联网单片机软硬件毕业生系统设计

avatar 亚马逊云科技技术品牌专区