【C++跬步积累】 —— 二叉搜索树（模拟实现+源代码）

于 2024-12-12 17:01:28 发布
阅读量793 收藏 26
点赞数 8
分类专栏： C++跬步积累 文章标签： c++ 开发语言 数据结构
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/PH_modest/article/details/144383604
版权

🌏博客主页：PH_modest的博客主页
🚩当前专栏：C++跬步积累
💌其他专栏：
🔴 每日一题
🟡 Linux跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

文章目录

二叉搜索树的概念

二叉搜索树（BST,Binary Search Tree）又称二叉排序数，它或者是一颗空树，或者是具有以下性质的二叉树：

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

注意： 由它的性质可以得出，中序遍历二叉搜索树得到的一组数据是有序的，中序遍历的顺序即是：左 - 根 - 右。

下图就是一个二叉搜索树：
在这里插入图片描述

二叉搜索树操作

在这里插入图片描述

 int  a[ ] = {8,3,1,10,6,4,7,14,13};

二叉搜索树的查找

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

二叉树的插入

  • 树为空，则直接新增节点，赋值给root指针
  • 树不空，按二叉搜索树性质查找插入位置，插入新节点

若不为空树，具体插入操作如下：

  1. 若待插入节点的值小于根节点的值，则需要将节点插入到左子树。
  2. 若待插入节点的值大于根节点的值，则需要将节点插入到右子树。
  3. 若待插入节点的值等于根节点的值，则插入失败。

在这里插入图片描述

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：

  1. 要删除的节点无孩子节点
  2. 要删除的节点只有左孩子节点
  3. 要删除的节点只有右孩子节点
  4. 要删除的节点有左、右孩子节点

看起来有待删除节点有4中情况，实际情况1可以与情况2或者3合并起来，因此真正的删除过程如下：

  • 情况2：删除该节点且使删除节点的双亲节点指向被删除节点的左孩子节点——直接删除。
  • 情况3：删除该节点且使删除节点的双亲节点指向被删除节点的右孩子节点——直接删除。
  • 情况4：在它的右子树中寻找中序下的第一个节点（关键码最小），用它的值填补到被删除节点中，再来处理该节点的删除问题——替换法删除

在这里插入图片描述

二叉搜索树的实现

节点类

要实现二叉搜索树，我们首先需要实现一个节点类：

  • 节点类中包含三个成员变量：节点值、左指针、右指针。
  • 节点类当中只需要实现一个构造函数即可，用于构造指定节点值的节点。
template<class K>
struct BSTreeNode
{
	K _key;					//节点值
	BSTreeNode<K>* _left;	//左节点
	BSTreeNode<K>* _right;	//右节点

	//构造函数
	BSTreeNode(const K& key = 0)
		:_val(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

构造函数

构造函数只需要创建一个空树即可：

BSTree()
		:_root(nullptr)
	{}

拷贝构造函数

	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;//返回拷贝的树
	}
	
	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);//拷贝二叉搜索树
	}

赋值运算符重载函数

在这里提供一个现代写法，使用swap函数，直接交换两个对象的二叉搜索树的根节点的指针，也就间接实现了二叉树的交换。注意是返回对象的引用，这样可以连续赋值，例如：a=b=c；

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

析构函数

析构函数可以调用一个_Destory()，通过_Destory()函数来逐个释放每个节点，因为析构函数不方便设置参数，所以可以通过定义一个私有的函数来封装一下，析构函数直接调用即可。

	void _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}
	~BSTree()
	{
		_Destory(_root);
		_root = nullptr;
	}

中序遍历

中序遍历暴露在外面的函数依旧是不带参数的，所以为了方便，可以定义一个子函数，通过调用子函数来进行封装。
思路：

  • 先判断是否为空，为空则直接退出
  • 然后通过 左 - 根 - 右 来进行遍历，通过该方式得到的数组是递增的
  • 可以通过递归调用，依次往下查找，先递归左子树
  • 当左子树递归到最深处时，会返回，然后遍历根，此时只需要输出当前值即可
  • 然后就是继续遍历右子树

该递归就是根据中序遍历的性质来写的，只需要考虑清楚什么时候输出值即可：遍历完左端点返回之后

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

	void Inoder()
	{
		_Inoder(_root);
		cout << "\n";
	}

插入函数

  • 首先任然需要先判断是不是空树，如果是空树，就直接在空节点上插入
  • 如果不是空树就遍历，按照搜索二叉树的特性，进行判断，直至找到正确的插入的点
  • 这里需要注意的是，需要定一个parent来存储上一个点的地址，便于将待插入的值连接上去
  • 最后连接时判断一下是连在左端点还是右端点
bool Insert(const K& key)
	{
		if (_root == nullptr)//空树
		{
			_root=new Node(key);
			return true;
		}
		//不为空
		//依次判断
		Node* parent = nullptr;
		Node* tmp = _root;
		while (tmp != nullptr)
		{
			if (tmp->_key > key)
			{
				parent = tmp;
				tmp = tmp->_left;
			}
			else if (tmp->_key <key)
			{
				parent = tmp;
				tmp = tmp->_right;
			}
			else
			{
				return false;
			}
		}
		tmp = new Node(key);
		if (key > parent->_key)
		{
			parent->_right = tmp;
		}
		else
		{
			parent->_left = tmp;
		}
		return true;
	}

删除函数

删除函数是二叉搜索树的重难点，难在需要分好几种情况讨论：

  1. 树为空，直接返回false；
  2. 待删除节点的左子树为空（左右子树都为空包含在内）；
  3. 待删除节点的右子树为空；
  4. 待删除节点的左右子树都不为空；

下面我们分情况单独讨论：

待删除节点的左子树为空

步骤：

  • 首先判断是否为根节点，如果是，则让根节点指向空；
  • 否则搜索找到该节点后，只需先让其父节点指向该节点的右孩子节点（这里需要判断待删除节点是其父节点的左子树还是右子树），然后将该节点释放，如此变完成了删除；

待删除节点的右子树为空

步骤：

  • 首先判断是否为根节点，如果是，则让根节点指向空；
  • 否则搜索找到该节点后，只需先让其父节点指向该节点的左孩子节点（这里需要判断待删除节点是其父节点的左子树还是右子树），然后将该节点释放，如此变完成了删除；

待删除节点的左右子树都不为空

步骤：

  • 替换法删除的核心就是找一个合适的数据与待删除节点的数据进行交换，那么应该如何找呢？
    • 找左节点的最大值
    • 找右节点的最小值
  • 这里我们以第二种为例，找之前需要定义两个变量：parentRight和minRight，第一个参数是待替换节点的父节点，用于连接待删除节点的右子树；第二个参数是待替换的节点，用来与待删除节点进行交换。
  • 接下来就是先找到右子树中最小的值，即找删除节点右子树中的左节点，找到之后进行值的替换
  • 然后parentRight需要连接minRight的右子树
  • 释放minRight
bool Erease(const K& key)
	{
		//树为空
		if (_root == nullptr)
		{
			return false;
		}
		//树不为空
		//先找是否存在
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//找到了
			{
				//左节点为空
				if (cur->_left == nullptr)
				{
					//为根节点，此时parent为nullptr
					if (cur->_key == _root->_key)
					{
						_root = cur->_right;
						return true;
					}
					//不为根节点
					//判断待删除节点大于parent还是小于parent(两种方法：比较值或者直接跟parent比较）
					if (cur->_key > parent->_key)//大于，右节点
					{
						parent->_right = cur->_right;
					}
					else//小于，左节点
					{
						parent->_left = cur->_right;
					}
					delete cur;
					cur = nullptr;
					return true;
				}
				//右节点为空
				if (cur->_right == nullptr)
				{
					//先判断是否为根节点
					if (cur->_key == _root->_key)
					{
						_root = cur->_left;
						return true;
					}
					//不为根节点
					//判断删除节点的子节点是parent的左孩子还是右孩子
					if (cur == parent->_left)//左节点
					{
						parent->_left = cur->_left;
					}
					else//右节点
					{
						parent->_right = cur->_left;
					}
					delete cur;
					cur = nullptr;
					return true;
				}
				//都不为空
				else
				{
					//替换法删除
					//找右子树中最小的节点
					Node* parentRight = cur;//待替换节点的父节点
					Node* minRight = cur->_right;//待替换的节点
					while (minRight->_left)
					{
						parentRight = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key;//替换值
					//注意一个隐藏条件：minRight的左节点为空
					//这部分判断不能省略，有两种情况：1.parentRight为待删除点；2.parentRight不为待删除点
					if (minRight == parentRight->_left)//parentRight不为待删除点
						parentRight->_left = minRight->_right;
					else//parentRight为待删除点
						parentRight->_right = minRight->_right;
					delete minRight;
					minRight = nullptr;
					return true;
				}
			}
		}
		return false;
	}

查找函数

查找函数根据二叉搜索树的性质遍历查找即可，注意最后没找到时返回空指针即可。

  1. 若树为空，则查找失败，返回nullptr;
  2. 若key值小于当前节点的值，则应该在该结点的左子树当中进行查找。
  3. 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
  4. 若key值等于当前结点的值，则查找成功，返回对应结点的地址。
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

二叉搜索树的应用

K模型

K模型，即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。

比如：给定一个单词，判断该单词是否拼写正确。具体方式如下：

  • 以单词集合中的每个单词作为key，构建一棵二叉搜索树。
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型

KV模型，对于每一个关键码key，都有与之对应的值value，即<key, value>的键值对。

比如：英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对。具体方式如下：

  • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到其对应的中文，英文单词与其对应的中文<word,chinese>就构成一种键值对；
  • 在比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word,count>就构成一种键值对。

二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2​N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N​

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了

二叉搜索树源代码

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

template<class K>
struct BSTreeNode
{
	K _key;					//节点值
	BSTreeNode<K>* _left;	//左节点
	BSTreeNode<K>* _right;	//右节点

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

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
private:
	Node* _root;

	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 _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}

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

public:
	//强制生成默认构造
	//BSTree() = default;

	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()
	{
		_Destory(_root);
		_root = nullptr;
	}

	void Inoder()
	{
		_Inoder(_root);
		cout << "\n";
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)//空树
		{
			_root=new Node(key);
			return true;
		}
		//不为空
		//依次判断
		Node* parent = nullptr;
		Node* tmp = _root;
		while (tmp != nullptr)
		{
			if (tmp->_key > key)
			{
				parent = tmp;
				tmp = tmp->_left;
			}
			else if (tmp->_key <key)
			{
				parent = tmp;
				tmp = tmp->_right;
			}
			else
			{
				return false;
			}
		}
		tmp = new Node(key);
		if (key > parent->_key)
		{
			parent->_right = tmp;
		}
		else
		{
			parent->_left = tmp;
		}
		return true;
	}

	bool Erease(const K& key)
	{
		//树为空
		if (_root == nullptr)
		{
			return false;
		}
		//树不为空
		//先找是否存在
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//找到了
			{
				//左节点为空
				if (cur->_left == nullptr)
				{
					//为根节点，此时parent为nullptr
					if (cur->_key == _root->_key)
					{
						_root = cur->_right;
						return true;
					}
					//不为根节点
					//判断待删除节点大于parent还是小于parent(两种方法：比较值或者直接跟parent比较）
					if (cur->_key > parent->_key)//大于，右节点
					{
						parent->_right = cur->_right;
					}
					else//小于，左节点
					{
						parent->_left = cur->_right;
					}
					delete cur;
					cur = nullptr;
					return true;
				}
				//右节点为空
				if (cur->_right == nullptr)
				{
					//先判断是否为根节点
					if (cur->_key == _root->_key)
					{
						_root = cur->_left;
						return true;
					}
					//不为根节点
					//判断删除节点的子节点是parent的左孩子还是右孩子
					if (cur == parent->_left)//左节点
					{
						parent->_left = cur->_left;
					}
					else//右节点
					{
						parent->_right = cur->_left;
					}
					delete cur;
					cur = nullptr;
					return true;
				}
				//都不为空
				else
				{
					//替换法删除
					//找右子树中最小的节点
					Node* parentRight = cur;//待替换节点的父节点
					Node* minRight = cur->_right;//待替换的节点
					while (minRight->_left)
					{
						parentRight = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key;//替换值
					//注意一个隐藏条件：minRight的左节点为空
					//这部分判断不能省略，有两种情况：1.parentRight为待删除点；2.parentRight不为待删除点
					if (minRight == parentRight->_left)//parentRight不为待删除点
						parentRight->_left = minRight->_right;
					else//parentRight为待删除点
						parentRight->_right = minRight->_right;
					delete minRight;
					minRight = nullptr;
					return true;
				}
			}
		}
		return false;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
};

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

int main()
{
	test1();
	return 0;
}
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

PH_modest

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值