当前位置： 首页 > article >正文

二叉搜索树的实现

article 2025/3/3 16:37:08

二叉搜索树（Binary Search Tree，BST）是一种基于二叉树的数据结构，具有以下特点：

  1. 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
  2. 左子树和右子树也都是二叉搜索树。

这个特性使得二叉搜索树能够高效地支持插入、删除和查找操作。

插入操作：
要在二叉搜索树中插入一个新节点，需要按照以下步骤进行：

  1. 如果树为空，则将新节点作为根节点。
  2. 如果树不为空，则从根节点开始比较新节点的值与当前节点的值。
  3. 如果新节点的值小于当前节点的值，继续在当前节点的左子树中插入新节点。
  4. 如果新节点的值大于当前节点的值，继续在当前节点的右子树中插入新节点。
  5. 重复步骤3和4，直到找到一个空位置插入新节点。

删除操作：
要在二叉搜索树中删除一个节点，需要按照以下步骤进行：

  1. 首先，找到要删除的节点。如果节点不存在，则删除操作失败。
  2. 如果要删除的节点没有子节点，直接删除即可。
  3. 如果要删除的节点只有一个子节点，将其子节点替代要删除的节点。
  4. 如果要删除的节点有两个子节点，需要找到其右子树中的最小节点（或左子树中的最大节点），将其值替换到要删除的节点上，然后删除这个最小（或最大）节点。

查找操作：
要在二叉搜索树中查找一个特定的值，需要按照以下步骤进行：

  1. 从根节点开始，将要查找的值与当前节点的值进行比较。
  2. 如果要查找的值等于当前节点的值，则找到了目标节点，返回该节点。
  3. 如果要查找的值小于当前节点的值，继续在当前节点的左子树中查找。
  4. 如果要查找的值大于当前节点的值，继续在当前节点的右子树中查找。
  5. 重复步骤3和4，直到找到目标节点或者遍历到叶子节点为止。

二叉搜索树的时间复杂度取决于树的平衡性。在最坏情况下，树可能变成链表，导致插入、删除和查找操作的时间复杂度为 O(n)。但是，如果树保持平衡，例如平衡二叉搜索树（AVL树、红黑树等），则这些操作的时间复杂度可以保持在 O(log n)。

以下是BST的代码实现：

定义BST的节点结构BSTreeNode，包含左子树指针_left、右子树指针_right和键值_key。

#include<iostream>
using namespace std;

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

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

定义BSTree类，其中的Find函数用于查找指定的键值。从根节点开始，根据当前节点的键值与目标键值的大小关系，沿着左子树或右子树逐步查找，直到找到目标键值或遍历完整个树。

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool 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 true;
		}
		return false;
	}

	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//不能在这更新parent,否则删除节点时parent和cur指向相同
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//删除操作
			{
				//只有一个孩子，托孤法				
				if (cur->_right == nullptr)//只有一个左孩子（+无孩子）
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
						delete cur;
						return true;
					}

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

					if (cur == parent->_left)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
					delete cur;
				}
				else //左右都有孩子
				{
					//有两个孩子，替换删除法；左子树的最大（最右）节点或右子数的最小（最左）节点
					//找到右子树的最左节点
					Node* subLeft = cur->_right;
					Node* subParent = cur;
					while (subLeft->_left)
					{
						subParent = subLeft;
						subLeft = subLeft->_left;
					}
					swap(subLeft->_key, cur->_key);
					//经过交换后，现在只需删除subLeft，已经转化为只有一个孩子的情况，使用托孤法
					if (subParent->_left == subLeft)
						subParent->_left = subLeft->_right;
					else
						subParent->_right = subLeft->_right;

					delete subLeft;
				}
				return true;
			}
		}
		return false;
	}

Erase函数用于删除指定的键值对应的节点。删除操作分为四种情况：

  1. 节点只有一个左孩子（包括无孩子），使用"托孤法"将其父节点指向其左孩子。
  2. 节点只有一个右孩子，同样使用"托孤法"将其父节点指向其右孩子。
  3. 节点既有左孩子又有右孩子，采用"替换删除法"，找到右子树的最左节点（或左子树的最右节点），将其键值与当前节点键值交换，然后删除这个最左节点。
  4. 无孩子可以随便合并到只有一个孩子的情况，代码是兼容的。

	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{	
				//parent = cur; 虽然写这里也可以，但是写在里面结构更清晰
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;
			}

			cur = new Node(key);
			parent->_key > cur->_key ? parent->_left = cur : parent->_right = cur;
		}
	}

insert函数用于插入一个新节点。若树为空，直接创建根节点；否则，从根节点开始，根据当前节点的键值与待插入键值的大小关系，沿着左子树或右子树逐步查找插入位置，直到找到一个空位置，然后创建新节点并插入。

	void midOrder()
	{
		_midOrder(_root);
	}
private:
	Node * _root = nullptr;

	void _midOrder(Node* node)
	{
		if (node == nullptr)
			return;

		_midOrder(node->_left);
		cout << node->_key << " ";
		_midOrder(node->_right);
	}
};

midOrder函数用于中序遍历树。由于根节点指针_root是私有的，无法在类外直接使用，因此提供了一个公有的无参遍历函数，在类内部调用私有的递归遍历函数_midOrder。

int main()
{
	int a[] = { 8,3,1,6,4,7,14,13 };
	BSTree<int> bst;
	for (int x : a)
	{
		bst.insert(x);
	}
	
	//测试：遍历删除
	for (int x : a)
	{
		bst.midOrder();
		cout << endl;
		bst.Erase(x);
		bst.midOrder();
		cout << endl;
		cout << endl;
	}

	cout << "全部删除成功" << endl;
	system("pause");
	return 0;
}

在主函数中，首先创建了一个BSTree对象bst，然后依次插入数组a中的元素。接下来进行遍历删除的测试，每次删除一个元素后，都会输出当前树的中序遍历结果。最后输出"全部删除成功"，并暂停程序的执行。

这段代码实现了BST的基本功能，包括查找、插入和删除操作，并且通过遍历删除的测试验证了代码的正确性。

完整代码如下:

#include<iostream>
using namespace std;

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

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

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool 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 true;
		}
		return false;
	}

	//删除节点，四种情况，可以合并为三种执行
	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//不能在这更新parent,否则删除节点时parent和cur指向相同
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//删除操作
			{
				//只有一个孩子，托孤法				
				if (cur->_right == nullptr)//只有一个左孩子（+无孩子）
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
						delete cur;
						return true;
					}

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

					if (cur == parent->_left)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
					delete cur;
				}
				else //左右都有孩子
				{
					//有两个孩子，替换删除法；左子树的最大（最右）节点或右子数的最小（最左）节点
					//找到右子树的最左节点
					Node* subLeft = cur->_right;
					Node* subParent = cur;
					while (subLeft->_left)
					{
						subParent = subLeft;
						subLeft = subLeft->_left;
					}
					swap(subLeft->_key, cur->_key);
					//经过交换后，现在只需删除subLeft，已经转化为只有一个孩子的情况，使用托孤法
					if (subParent->_left == subLeft)
						subParent->_left = subLeft->_right;
					else
						subParent->_right = subLeft->_right;

					delete subLeft;
				}
				return true;
			}
		}
		return false;
	}

	//插入节点，要保证插入的值不同，一旦发现相同的，返回false
	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{	
				//parent = cur; 虽然写这里也可以，但是写在里面结构更清晰
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;
			}

			cur = new Node(key);
			parent->_key > cur->_key ? parent->_left = cur : parent->_right = cur;
		}
	}

	//遍历树需要传根节点指针，但是树的指针是私有的
	//解决方法：套一层壳，给用户提供无参的遍历函数，在类内部调用传参遍历函数
	void midOrder()
	{
		_midOrder(_root);
	}
private:
	Node * _root = nullptr;

	void _midOrder(Node* node)
	{
		if (node == nullptr)
			return;

		_midOrder(node->_left);
		cout << node->_key << " ";
		_midOrder(node->_right);
	}
};


int main()
{
	int a[] = { 8,3,1,6,4,7,14,13 };
	BSTree<int> bst;
	for (int x : a)
	{
		bst.insert(x);
	}
	
	//测试：遍历删除
	for (int x : a)
	{
		bst.midOrder();
		cout << endl;
		bst.Erase(x);
		bst.midOrder();
		cout << endl;
		cout << endl;
	}

	cout << "全部删除成功" << endl;
	system("pause");
	return 0;
}


http://www.kler.cn/a/104524.html

相关文章：

  • 外汇天眼：获利数倍、财务自由不是梦？ 小心网络投资诈骗4阶段！
  • 文件加密丨最值得收藏的3种方法
  • 数据安全法开始正式实施的时间是什么时候？主要目的是什么？
  • 用Python做数据分析之数据处理及数据提取
  • DASCTF X CBCTF 2023
  • Linux 用户必备的 Git 图形化工具
  • 探索未来的视觉革命：卷积神经网络的崭新时代（二）
  • 未能为 SSL/TLS 安全通道建立信任关系
  • uniapp中 background-image 设置背景图片不展示问题
  • 01 # 手写 new 的原理
  • JVM重点
  • 刷题笔记day01-数组
  • 2520. 统计能整除数字的位数 : 简单模拟题（时空复杂度最优解）
  • docker搭建个人镜像仓库
  • css-边框流水线
  • Spirit：继承 gh-ost 灵魂的 MySQL 在线大表变更方案
  • 图论02-【无权无向】-图的深度优先遍历DFS
  • VUE父组件向子组件传递数据和方法
  • 【嵌入式项目应用】__cJSON在单片机的使用
  • 威联通NAS进阶玩法之使用Docker搭建个人博客教程