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

【C++】模拟实现一颗二叉搜索树

article 2025/4/1 4:27:14
❤️欢迎来到我的博客❤️

前言

搜索二叉树是在二叉树的基础上加了一个特征：左子树的所有节点都小于根，右子树的所有节点都大于根（每一颗子树都要满足）
因为这个特性的存在，使得他特别擅长搜索数据
比如我要寻找10，如果当前根为6，比10小，根据这个特征我们就可以排除左子树的节点（都是比6小的数），直接去右子树中寻找
如果当前根为11，比10大，那么我们就可以排除右子树当中所有的数据，直接去左子树中寻找
搜索二叉树也叫二叉搜索树、二叉排序树：当搜索二叉树走中序遍历，他就是一个有序的状态->左->根->右

时间复杂度

在这里插入图片描述
在这里插入图片描述

以上都是二叉搜索树，但他们的时间复杂度却是不一样的，所以时间复杂度为最多找高度次（最坏的情况）：O(N)
后续的AVL树和红黑树都是针对这种情况做出的优化：O(logN)

二叉搜索树的模拟实现

整体框架 / insert / inorder

普通二叉树的增删查改是没有价值的，因为数据没有固定的插入位置，所以普通二叉树可以用链表替代
但是二叉搜索树插入的数据就有意义了，因为他们需要插入到他们需要到的位置

在这里插入图片描述
插入模式：
比如我们要插入一个11，那我们的顺序就是：根->右->右->左->左插入
如果要插入一个13，顺序是：根->右->右->左，发现已经存在13（目前阶段不允许出现重复数据），插入失败
插入一个16，那我们的顺序就是：根->右->右->右插入

#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:
	BSTree()
		:_root(nullptr)
	{ }

	bool Insert(const K& key)
	{
		//如果是空树
		if (_root == nullptr)
		{
			//直接new一个
			_root = new Node(key);
			return true;
		}

		//循环插入版本
		Node* parent = nullptr;
		Node* cur = _root;
		//如果cur不为空，则去找位置
		while (cur)
		{
			// 当前节点值 < 插入值 → 向右子树查找
			if (cur->_key < key)
			{
				// 记录父节点
				parent = cur;
				//走右子树
				cur = cur->_right;
			}
			else if (cur->_key > key)	// 当前节点值 > 插入值 → 向左子树查找
			{
				// 记录父节点
				parent = cur;
				//走左子树
				cur = cur->_left;
			}
			else
			{
				//如果值存在则插入失败
				return false;
			}
		}

		//走到指定位置
		cur = new Node(key);
		// 判断插入方向
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

	//类外面拿不到私有成员
	//单独写一个函数来调用
	void InOrder()
	{
		_InOrder(_root);
	}

	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		// 递归中序遍历
		_InOrder(root->_left);		  //左
		cout << root->_key << " ";	 //根
		_InOrder(root->_right);	    //右
	}
private:
	Node* _root; // 根节点指针
};

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}
	
	t.InOrder();// 输出：1 3 4 6 7 8 10 13 14（有序验证BST正确性）

	return 0;
}

运行结果：
在这里插入图片描述

查找

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;
}

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	cout << t.Find(13) << endl;
	cout << t.Find(15) << endl;
	return 0;
}

运行结果：
在这里插入图片描述

删除

在这里插入图片描述
如果我们要删除7，是属于直接删除的场景，实现起来比较容易（特征：没有孩子）
如果要删除14，也是比较好实现的删除之后，只需要链接一下即可（特征：只有一个孩子）
但是如果我们要删除的是8呢，那要考虑的就多了（特征：两个孩子）这时候就要用替换法（左子树的最大节点（最右节点），或者右子树的最小节点（最左节点））来实现

bool Erase(const K& key)
{
	Node* parent = nullptr;	 // 记录当前节点的父节点
	Node* cur = _root;      // 从根节点开始查找

	//查找
	while (cur)
	{
		//使用Find函数做起来会比较麻烦
		//不考虑服用Find
		if (cur->_key < key)		// 目标值在右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)	// 目标值在左子树
		{
			parent = cur;
			cur = cur->_left;
		}
		else //找到了
		{
			//情况1：左子树为空（含叶子节点）
			if (cur->_left == nullptr)
			{
				//处理根节点情况
				if (cur == _root)
				{
					// 根指向右子树
					_root = cur->_right;
				}
				else
				{
					// 判断当前节点是父节点的左/右孩子
					if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
				}
			}//情况2：右子树为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
			}//情况3：左右子树均不为空（替换法）
			else
			{
				// 查找左子树最大节点作为替代节点
				Node* parent = cur;				// 记录替代节点的父节点
				Node* leftMax = cur->_left;		// 进入左子树

				// 一直向右找到最右节点（左子树最大值）
				while (leftMax->_right)
				{
					parent = leftMax;
					leftMax = leftMax->_right;
				}

				// 交换当前节点与替代节点的值
				swap(cur->_key, leftMax->_key);

				// 删除替代节点（此时maxLeft右子树必为空）
				if (parent->_left == leftMax)
				{
					// 若替代节点是父的左孩子，链接其左子树
					parent->_left = leftMax->_left;
				}
				else
				{
					// 若替代节点是父的右孩子，链接其左子树
					parent->_right = leftMax->_left;
				}

				cur = leftMax;
			}

			delete cur;		// 释放替代节点
			return true;	// 删除成功
		}
	}
	return false; // 未找到目标节点
}

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();
	t.Erase(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	//删空
	for (auto e : a)
	{
		t.Erase(e);
	}
	
	cout << "当前树：";
	t.InOrder();
	return 0;
}

运行结果：
在这里插入图片描述

删除总结

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

删除逻辑分布解析

二叉搜索树删除操作分步解析

1. 查找待删除节点

核心逻辑：从根节点出发，根据BST特性向左或向右搜索目标值。
终止条件：

  • 找到目标节点（cur->_key == key）
  • 遍历到空节点（cur == nullptr），说明目标不存在

2. 处理删除的三种情况

情况1：左子树为空

特征：待删节点无左孩子（可能为叶子节点或仅有右子树）
操作步骤：

  1. 根节点处理：

    • 若删除的是根节点，直接让根指向右子树
    • _root = cur->_right;

  2. 非根节点处理：

    • 若待删节点是父节点的右孩子：
    • parent->_right = cur->_right;
    • 若待删节点是父节点的左孩子：
    • parent->_left = cur->_right;

情况2：右子树为空

特征：待删节点无右孩子（仅有左子树）
操作步骤（与情况1对称）：

  1. 根节点处理：
    • _root = cur->_left;

2.非根节点处理：

  • 若待删节点是父节点的右孩子：
  • parent->_right = cur->_left;
  • 若待删节点是父节点的左孩子：
  • parent->_left = cur->_left;

情况3：左右子树均不为空

核心思想：找到替代节点替换待删节点的值，再删除替代节点
步骤详解：
步骤1：查找替代节点：两种方案选一即可

方案一：左子树最大节点

Node* parent = cur;				// 记录替代节点的父节点
Node* leftMax = cur->_left;		// 进入左子树

// 一直向右找到最右节点（左子树最大值）
while (leftMax->_right)
{
	parent = leftMax;
	leftMax = leftMax->_right;
}

方案二：右子树最小节点

Node* minParent = cur;        // 初始化替代节点的父节点为当前节点
Node* minRight = cur->_right; // 进入右子树

// 找到右子树的最左节点（最小值节点）
while (minRight->_left) 
{     
    minParent = minRight;
    minRight = minRight->_left;
}

步骤2：值替换

// 交换当前节点与替代节点的值
swap(cur->_key, leftMax->_key);

步骤3：删除替代节点

// 删除替代节点（此时maxLeft右子树必为空）
if (parent->_left == leftMax)
{
	// 若替代节点是父的左孩子，链接其左子树
	parent->_left = leftMax->_left;
}
else
{
	// 若替代节点是父的右孩子，链接其左子树
	parent->_right = leftMax->_left;
}

cur = leftMax;

递归版本

#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:
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		Destroy(_root);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	// 递归查找入口函数
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	// 递归插入入口函数
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	// 递归删除入口函数
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

private:
	// 递归删除实现（参数为节点指针的引用，确保树结构正确更新）
	bool _EraseR(Node*& root, const K& key)
	{
		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// 找到目标节点
		{
			Node* del = root;

			//1、左为空
			//2、右为空
			//3、左右都不为空
			if (root->_left == nullptr)	//左子树为空
			{
				root = root->_right;	// 直接让父节点指针指向右子树
			}
			else if (root->_right == nullptr)	//右子树为空
			{
				root = root->_left;		//直接让父节点指针指向左子树
			}
			else	//左右子树均非空
			{
				Node* leftMax = root->_left;	//找到左子树最大节点（最右节点）
				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}

				swap(root->_key, leftMax->_key);//交换当前节点与左子树最大节点的键值

				return _EraseR(root->_left, key);//递归删除左子树中的原最大节点
			}

			delete del;
			return true;
		}
	}

	//递归插入实现（参数为节点指针的引用，确保树结构正确更新）
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			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 _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
		{
			return true;
		}
	}
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		// 递归中序遍历
		_InOrder(root->_left);		  //左
		cout << root->_key << " ";	 //根
		_InOrder(root->_right);	    //右
	}

	Node* _root; //根节点指针
};

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.InsertR(e);
	}

	t.InOrder();

	t.EraseR(4);
	t.InOrder();

	t.EraseR(6);
	t.InOrder();

	t.EraseR(7);
	t.InOrder();

	t.EraseR(3);
	t.InOrder();

	for (auto e : a)
	{
		t.EraseR(e);
	}
	t.InOrder();

	return 0;
}

运行结果：
在这里插入图片描述

Copy和Destroy

#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:
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		Destroy(_root);
	}
private:
	Node* Copy(Node* root)
	{
		//递归终止条件
		if (root == nullptr)
		{
			return nullptr;
		}
		//创建当前节点的副本（深拷贝键值）
		Node* copyroot = new Node(root->_key);

		//递归拷贝左子树，并正确链接到副本节点的左指针
		copyroot->_left = Copy(root->_left);

		//递归拷贝右子树，并正确链接到副本节点的右指针
		copyroot->_right = Copy(root->_right);

		//返回当前子树副本的根节点
		return copyroot;
	}

	void Destroy(Node*& root) 
	{
		//递归终止条件：当前节点为空，无需处理
		if (root == nullptr) 
		{
			return;
		}
		//递归销毁左子树
		Destroy(root->_left);
		//递归销毁右子树
		Destroy(root->_right);
		//释放当前节点内存
		delete root;
		//将当前指针置空
		root = nullptr;
	}
};

key / value模型

节点结构：
每个节点包含Key、Value和左右子节点指针

排序规则：
树的结构依然基于key 的大小关系维护，value不参与运算
左子树所有节点的key < 当前节点的key
右子树所有节点的key > 当前节点的key

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

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

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

	private:
		bool _EraseR(Node*& root, const K& key)
		{
			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
			{
				Node* del = root;

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}

					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return true;
			}

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

		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;

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

		void _InOrder(Node* root)
		{
			if (root == NULL)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

}

int main()
{
	key_value::BSTree<string, string> dict;
	dict.InsertR("insert", "插入");
	dict.InsertR("sort", "排序");
	dict.InsertR("right", "右边");
	dict.InsertR("date", "日期");

	string str;
	while (cin >> str)
	{
		auto ret = dict.FindR(str);
		if (ret)
		{
			cout << ret->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}

	return 0;
}

运行效果：

在这里插入图片描述

统计次数场景

修改后的InOrder:

void _InOrder(Node* root)
{
	if (root == NULL)
	{
		return;
	}

	_InOrder(root->_left);
	cout << root->_key << ":" << root->_value << endl;
	_InOrder(root->_right);
}

int main()
{
	//统计水果出现的次数
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	key_value::BSTree<string, int> countTree;

	//遍历水果
	for (auto& str : arr)
	{
		//在树中查找当前水果名称对应的节点
		auto ret = countTree.FindR(str);
		// 情况1：水果未存在于树中（首次出现）
		if (ret == nullptr)
		{
			//插入新节点：为水果名，初始次数为1
			countTree.InsertR(str, 1);
		}
		else// 情况2：水果已存在于树中
		{
			//递增该水果的计数
			ret->_value++;
		}
	}

	//次数统计完成，遍历这棵树
	countTree.InOrder();

	return 0;
}

运行结果：

在这里插入图片描述

以上就是本篇文章的全部内容了，希望大家看完能有所收获

❤️创作不易，点个赞吧❤️

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

相关文章：

  • LeeCode 434. 字符串中的单词数
  • MySQL（数据表创建）
  • Paddlex服务化代理处理跨域、替换Response中Json key
  • 【质量管理】防错（POKA-YOKE）的概念、特点和作用解析
  • 3、fabric实现多机多卡训练
  • PoE交换机如何助力智慧城市基础设施建设？
  • Nginx RTMP DASH 模块分析 (ngx_rtmp_dash_module.c)
  • 基于Springboot的网上订餐系统 【源码】+【PPT】+【开题报告】+【论文】
  • 认识一家公司：瑞芯微（Rockchip Electronics Co., Ltd.）以及旗下的两款芯片RK3288\RK3588
  • PHP接口开发：从基础到高级的全面指南
  • 【强化学习】基于深度强化学习的微能源网能量管理与优化策略研究【Python】
  • 调用阿里云API实现快递地址解析
  • 力扣hot100——搜索二维矩阵
  • Android读写权限分析
  • MFC(1)-odbc-ado-调用mysql,sqlserver
  • AI大模型从0到1记录学习 day08
  • Go 语言标准库中encoding/xml模块详细功能介绍与示例
  • 【QT5 多线程示例】异步编程
  • Java 实现将Word 转换成markdown
  • fyrox 2D和3D游戏的制作