【C++】：搜索二叉树

2023-12-15 02:55:44

朋友们、伙计们，我们又见面了，本期来给大家解读一下有关多态的知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语 言 专 栏：C语言：从入门到精通

数据结构专栏：数据结构

个? 人? 主? 页?：stackY、

C + + 专 栏? ?：C++

Linux 专?栏? ：Linux

??

目录

1. 搜索二叉树

1.1 概念

1.2 搜索二叉树操作

2. 模拟实现搜索二叉树?

2.1 非递归版本

2.1.1 基本构造

2.1.2 插入

2.1.3 删除

2.1.4 查找

2.2 递归版本

2.2.1 插入

2.2.2 删除

2.2.3 查找

2.2.4?中序遍历

3. 完整代码

1. 搜索二叉树

1.1 概念

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

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

1.2 搜索二叉树操作

?

1. 二叉树的查找

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

2. 二叉树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

3. 二叉树的删除?

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

2. 模拟实现搜索二叉树?

搜索二叉树有两种模型：

1. Key模型：节点中只存在一个值key，并且这个值不可以修改，比如后面学习到的set

2. Key_Value模型：节点中存在两个值，一个是key，不可修改，另一个是与key对应的value，可以修改，比如后面学习到的map

在这里我们只实现Key模型的搜索二叉树

2.1 非递归版本

2.1.1 基本构造
//节点
template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

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

//搜索二叉树
template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;

	//构造
	BSTree() //给定了缺省值
	{}
	//拷贝构造
	BSTree(const BSTree<K>& tmp)
	{
		_root = Copy(tmp._root);
	}
	//operator=
	BSTree<K> operator=(BSTree<K> tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}
	//析构
	~BSTree()
	{
		Destroy(_root);
	}
private:
    //递归拷贝左右子树
	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;
	}
    //后序遍历删除
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

private:
	Node* _root = nullptr;  //缺省值给空即可
};
2.1.2 插入

插入时如果为空直接插入即可，若存在节点，需要先进行判断，比根节点大的插入到它的右子树，比根节点小的插入左子树即可，这时需要注意的插入的节点需要与它的父节点进行链接，这时在往下比较的过程中就需要记录一下它的父节点。

//插入
	bool Insert(const K& key)
	{
		//如果为空可以直接插入链接
		if (_root == nullptr)
		{
			_root = new Node(key);
			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);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
2.1.3 删除

首先找到需要删除的节点，删除的时候需要注意分下面几种情况：

  • 左子树为空，可以直接删除
  • 右子树为空，可以直接删除
  • 左右子树都不为空需要使用替换法删除
  • 替换法：使用左子树最大的节点替换需要删除的节点，或者使用右子树最小的节点替换需要删除的节点，替换之后直接删除被替换的节点即可完成删除。
  • 需要注意的是在这个过程中需要记录父节点，在删除之后需要及时链接，并且要注意的是删除的节点是根节点的时候可以直接将它的左右子树直接链接。
//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		//记录父亲
		Node* parent = nullptr;
		while (cur)
		{
			//找到要删除的key
			if (cur->_key > key)
			{
				//更新父亲
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//开始删除
				if (cur->_left == nullptr) //左为空  //直接删除
				{
					//先判断是否为根节点
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else  //不为根节点
					{
						if (cur == parent->_left) 
						{
							parent->_left = cur->_right;
						}
						else if (cur == parent->_right)
						{
							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 if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else    //左右子树都不为空  //使用替换法
				{
					Node* parent = cur;
					//右树的最小节点进行替换或者左树的最大节点
					Node* subRight = cur->_right;
					while (subRight->_left)  //找到右树的最小节点
					{
						parent = subRight;
						subRight = subRight->_left;
					}

					swap(cur->_key, subRight->_key);  //替换两个节点

					//将删除节点的右树链接在它的父亲
					if (parent->_left == subRight)
					{
						parent->_left = subRight->_right;
					}
					else 
					{
						parent->_right = subRight->_right;
					}
					delete subRight;
				}
				return true;
			}
		}
		return false;
	}
2.1.4 查找
//查找
	bool 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 true;
		}
		return false;
	}

2.2 递归版本

2.2.1 插入

递归插入时也需要进行一层封装，在里面传递root，在这里采用引用传参比较好，可以不用额外的链接，遇到空直接创建一个节点即可，直接在原数上进行操作。

//插入
	bool InsertR(const K& key)
	{
		return _InsertR(key, _root);
	}

bool _InsertR(const K& key, Node*& root)
	{
		//树为空直接插入即可
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		//递归左
		if (root->_key > key)
			return _InsertR(key, root->_left);
		else if (root->_key < key)  //递归右
			return _InsertR(key, root->_right);
		else
			return false;
	}
2.2.2 删除

还是采用里面封装一层，在递归删除的时候先递归找到要删除的key，然后判断它的左右子树，如果左右子树只存在一个可以直接进行删除，然后将它的孩子链接在它的节点上，如果左右孩子均存在，使用替换法，用该节点的右子树的最小节点进行替换，先使用循环找到该最小节点，然后与其交换，然后转化为递归该节点右子树的删除问题即可。

//删除
	bool EraseR(const K& key)
	{
		return _EraseR(key, _root);
	}
bool _EraseR(const K& key, Node*& root)
	{
		if (root == nullptr)
			return false;
		//查找key
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else  //找到了进行删除操作
		{
			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* subRight = root;  //找到右树的最小节点
				while (subRight->left)
				{
					subRight = subRight->_left;
				}
				swap(root->_key, subRight->_key);  //交换
				
				return _EraseR(key, root->_right);   //转化为递归右子树的子问题
			}
		}
	}
2.2.3 查找
//查找
	bool FindR(const K& key)
	{
		_FindR(key, _root);
	}
bool _FindR(const K& key, Node* root)
	{
		if (root == nullptr)
			return false;
		if (root->_key > key)
			return _FindR(root->_left);
		else if (root->_key < key)
			return _FindR(root->_right);
		else
			return true;
	}
2.2.4?中序遍历

中序遍历时需要封装一层，在外面不好传递节点，中序遍历：左子树、根、右子树

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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

3. 完整代码

#pragma once
#include <iostream>

using namespace std;

template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;

	//构造
	BSTree() //给定了缺省值
	{}
	//拷贝构造
	BSTree(const BSTree<K>& tmp)
	{
		_root = Copy(tmp._root);
	}
	//operator=
	BSTree<K> operator=(BSTree<K> tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}
	//析构
	~BSTree()
	{
		Destroy(_root);
	}

	//非递归版本
	//插入
	bool Insert(const K& key)
	{
		//如果为空可以直接插入链接
		if (_root == nullptr)
		{
			_root = new Node(key);
			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);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	//删除
	bool Erase(const K& key)
	{
		Node* cur = _root;
		//记录父亲
		Node* parent = nullptr;
		while (cur)
		{
			//找到要删除的key
			if (cur->_key > key)
			{
				//更新父亲
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//开始删除
				if (cur->_left == nullptr) //左为空  //直接删除
				{
					//先判断是否为根节点
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else  //不为根节点
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else if (cur == parent->_right)
						{
							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 if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else    //左右子树都不为空  //使用替换法
				{
					Node* parent = cur;
					//右树的最小节点进行替换或者左树的最大节点
					Node* subRight = cur->_right;
					while (subRight->_left)  //找到右树的最小节点
					{
						parent = subRight;
						subRight = subRight->_left;
					}

					swap(cur->_key, subRight->_key);  //替换两个节点

					//将删除节点的右树链接在它的父亲
					if (parent->_left == subRight)
					{
						parent->_left = subRight->_right;
					}
					else
					{
						parent->_right = subRight->_right;
					}
					delete subRight;
				}
				return true;
			}
		}
		return false;
	}

	//查找
	bool 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 true;
		}
		return false;
	}

	
	//递归版本
	//插入
	bool InsertR(const K& key)
	{
		return _InsertR(key, _root);
	}
	//删除
	bool EraseR(const K& key)
	{
		return _EraseR(key, _root);
	}
	//查找
	bool FindR(const K& key)
	{
		_FindR(key, _root);
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	//插入
	bool _InsertR(const K& key, Node*& root)
	{
		//树为空直接插入即可
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		//递归左
		if (root->_key > key)
			return _InsertR(key, root->_left);
		else if (root->_key < key)  //递归右
			return _InsertR(key, root->_right);
		else
			return false;
	}
	//删除
	bool _EraseR(const K& key, Node*& root)
	{
		if (root == nullptr)
			return false;
		//查找key
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else  //找到了进行删除操作
		{
			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* subRight = root;  //找到右树的最小节点
				while (subRight->left)
				{
					subRight = subRight->_left;
				}
				swap(root->_key, subRight->_key);  //交换

				return _EraseR(key, root->_right);   //转化为递归右子树的子问题
			}
		}
	}
	//查找
	bool _FindR(const K& key, Node* root)
	{
		if (root == nullptr)
			return false;
		if (root->_key > key)
			return _FindR(root->_left);
		else if (root->_key < key)
			return _FindR(root->_right);
		else
			return true;
	}
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	//拷贝
	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;
	}
	//销毁
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
private:
	Node* _root = nullptr;
};

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！?????

文章来源:https://blog.csdn.net/Yikefore/article/details/134539937
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。