【C++】二叉搜索树

风中的云彩

发布于 2025-04-11 02:18:07

9500

代码可运行

文章被收录于专栏：C/C++的自学之路C/C++的自学之路

运行总次数：0

代码可运行

前言

这是我自己学习C++的第十三篇博客总结。后期我会继续把C++学习笔记开源至博客上。 上一期笔记是关于C++的多态知识，没看的同学可以过去看看： 【C++】多态-CSDN博客

https://cloud.tencent.com/developer/article/2509504

二叉搜索树的概念

二叉搜索树，又称二叉排序树，如果其不为空，则具有以下性质：

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

二叉搜索树的性能

完全二叉树概念

完全二叉树：除了最后一层，其他层的节点都被完全填满，并且最后一层的节点从左到右依次排列的树形结构。

搜索二叉树的性质

最优情况下，二叉搜索树接近完全二叉树，其高度为

。

最差情况下，二叉搜索树接近单支树，其高度为

。

二叉搜索树越平衡，搜索的效率就越高。

二叉搜索树的优势

二分查找也能实现

效率级别的查找，但是存在以下两个不足：

需要储存在数组中，而且需要提前进行排序。
插入删除数据的效率很低。

模拟实现二叉搜索树

需要实现插入、删除、查找、中序遍历四个接口。 插入时：树为空，则直接新增结点，赋值给root指针；树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位；如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。 查找时：从根节点开始比较，查找x，x比根节点的值大则往右边走，x比根值小则往左边走。最多查找二叉搜索树的高度次，走到到空，如果还没找到，则这个值不存在。如果不支持插入相等的值，找到x即可返回，如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。首先查找元素是否在二叉搜索树中，如果不存在，则返回false。如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

要删除结点N左右孩子均为空
要删除的结点N左孩子位空，右孩子结点不为空
要删除的结点N右孩子位空，左孩子结点不为空
要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案：

情况1可以当成情况2或者情况3处理，效果相同。
把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点。
把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点。
无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R或者N右子树的值最小结点R替代N，因为这两个结点中任意⼀个，放到N的位置，都满足二叉搜索树的规则。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

template<class T>
struct BSTNode
{
	typedef BSTNode<T> Node;
public:
	BSTNode(const T& x)
		:_key(x)
		,_left(nullptr)
		, _right(nullptr)
	{}

	T _key;
	Node* _left;
	Node* _right;
};

template<class T>
class BSTree
{
	typedef BSTNode<T> Node;
	typedef BSTree<T> Tree;
public:
	BSTree()
		:_root(nullptr)
	{}
	bool insert(const T& x)
	{
		Node* cur = _root;//从根节点开始查找
		Node* parent = nullptr;
		if (_root == nullptr)
		{
			_root = new Node(x);
			return true;
		}
		else
		{
			while (cur != nullptr)
			{
				if (cur->_key < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;//不能插入已有的值
				}
			}
		}
		cur = new Node(x);
		if (parent->_key < cur->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	bool erase(const T& x)
	{
		Node* parent = nullptr;
		Node* cur = _root;//从根节点开始查找
		while (cur != nullptr)
		{
			if (cur->_key < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
                //找到了x,cur指向x的节点
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else 
						{
							parent->_right = cur->_right;
						}
					}
				}
				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;
						}
					}
				}
				else
				{
                    //cur的左右节点都不为空
					//找右子树的最小节点
					Node* minright = cur->_right;
					Node* parent_minright = cur;
					while(minright->_left!= nullptr)
					{
						parent_minright = minright;
						minright = minright->_left;
					}
					cur->_key = minright->_key;
					if (parent_minright->_left == minright)
					{
						parent_minright->_left = minright->_right;
					}
					else
					{
						parent_minright->_right = minright->_right;
					}
				}
				return true;
			}
		}
		return false;
	}
	Node* Find(const T& x)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < x)
			{
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		else
		{
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	}
	Node* _root;
};

int main()
{
	
	BSTree<int> t1;
	t1.insert(2);
	t1.insert(1);
	t1.insert(3);
	t1.insert(5);
	t1.insert(4);
	t1.insert(0);
	t1.InOrder();
	cout << t1.Find(4) << endl;
	t1.erase(3);
	t1.InOrder();
	return 0;
}

key-value模拟实现二叉搜索树

只需要在二叉树节点的构造时，设置两个值key-value即可。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

template<class T,class V>
struct BSTNode
{
	typedef BSTNode<T,V> Node;
public:
	BSTNode(const T& x,const V& y)
		:_key(x)
		,_val(y)
		, _left(nullptr)
		, _right(nullptr)
	{}

	T _key;
	V _val;
	Node* _left;
	Node* _right;
};

template<class T, class V>
class BSTree
{
	typedef BSTNode<T,V> Node;
	typedef BSTree<T,V> Tree;
public:
	BSTree()
		:_root(nullptr)
	{}
	bool insert(const T& x, const V& y)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		if (_root == nullptr)
		{
			_root = new Node(x,y);
			return true;
		}
		else
		{
			while (cur != nullptr)
			{
				if (cur->_key < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
		}
		cur = new Node(x,y);
		if (parent->_key < cur->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	bool erase(const T& x)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			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;
						}
					}
				}
				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;
						}
					}
				}
				else
				{
					//找右子树的最小节点
					Node* minright = cur->_right;
					Node* parent_minright = cur;
					while (minright->_left != nullptr)
					{
						parent_minright = minright;
						minright = minright->_left;
					}
					cur->_key = minright->_key;
					if (parent_minright->_left == minright)
					{
						parent_minright->_left = minright->_right;
					}
					else
					{
						parent_minright->_right = minright->_right;
					}
				}
				return true;
			}
		}
		return false;
	}
	Node* Find(const T& x)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < x)
			{
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		else
		{
			_InOrder(root->_left);
			cout << root->_key<<" " << root->_val << "  ";
			_InOrder(root->_right);
		}
	}
	Node* _root;
};

int main()
{

	BSTree<int,int> t1;
	t1.insert(2,11);
	t1.insert(1,12);
	t1.insert(3,13);
	t1.insert(5,14);
	t1.insert(4,15);
	t1.insert(0,16);
	t1.InOrder();
	cout << t1.Find(4) << endl;
	t1.erase(3);
	t1.InOrder();
	return 0;
}