【数据结构取经之路】二叉搜索树的实现

  • 开发
  • 17

目录

前言

二叉搜索树

概念

性质

二叉搜索树的实现

结点的定义

插入

查找

删除

二叉搜索树完整代码

前言

首先，二叉搜索树是一种数据结构，了解二叉搜素树有助于理解map和set的特性。

二叉搜索树

概念

二叉搜索树又称二叉排序树，它也可能是一棵空树，走中序遍历得到的结果是有序的。

性质

二叉搜索树如果不为空，它应满足一下性质：

● 每一个节点都有一个键值，而且每一个键值唯一标识一个节点（即二叉搜索树所有节点中没有重复的值）

● 假设根节点的值为X，那么它的左子树上的所有节点的值都小于X，右子树上的所有的结点的值都大于X

● 根的左右子树都是二叉搜索树（递归性质）

二叉搜索树的实现

二叉搜索树的基本操作有插入、查找、删除，其中插入和查找好说，最麻烦的是它的删除操作。

结点的定义

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

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

插入

例如要插入0，0比8小，往左走，遇到3，0比3小，往左走，遇到1，0比1小，往左走，遇到空， 此时可以进行插入了。 总结起来就是：遇到空就可以插入。

直接上代码，后边再总结细节~

bool Insert(const K& key)
{
    //如果根节点为空，第一个插入的结点就充当根节点
	if (_root == nullptr)
	{
		Node* newNode = new Node(key);
		_root = newNode;
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	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->_key == key，该值插入进入会破坏键值的唯一性，故插入失败
		}
	}

    //不知道上述代码是往左走到空还是往右走到空，
    //所以不确定是插入左边还是右边，需要判断
	Node* newNode = new Node(key);
	if (parent->_key > key)
		parent->_left = newNode;
	else
		parent->_right = newNode;

	return true;
}

细节：

● 要记录当前结点的父节点，否则当前结点走到空了新插入的结点无法链接上

● 如果要插入的元素在树中已存在，应该禁止插入，以免破坏键值的唯一性

● 如果根节点为空，则第一个插入的结点充当根节点

● 在插入前，要判断插入左边还是右边，因为我们不知道是往左走到空还是往右走到空而跳出循环来到执行插入的代码的

查找

● 从根开始比较，比根大的往右走查找，比根小的往左走查找

● 最多查找高度次，走到空，还没找到，说明这个值不存在

代码：


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

删除

上面的都好说，删除才是重头戏。

首先，查找所删除的结点是否在二叉搜索树中，如果不存在则返回false，如果存在就有以下几种情况。

1）要删除的节点为叶子结点

2）要删除的结点只有左孩子或只有右孩子

3）要删除的结点左右孩子均存在

针对第一种情况，直接删除就好，没什么好说的。

针对第二种情况，请看下面分析。

例如要删除的结点为14，根据上图，我们只需要将结点10的指向调整一下，让它指向13就可以了。当然，我们还要记录被删除结点的父节点才可以正确调整指向。仔细想想，就会返现，情况1和情况2是可以一起处理的。

第三种情况：

 

例如要删除结点3，根据上图，如果我们直接删除肯定是不对的，得用替换法来删除。用谁来替换是有讲究的，我们可以选择使用节点3的左子树的最大值或者是节点3右子树的最小值，简记：左的最大，右的最小。处理成下面这样：

 处理成这样后，删除掉rightMin节点即可。当然，rightMin节点也可能有右孩子（它不可能有左孩子，因为我们找的是右子树的最小值，必然是右子树中的最左节点），我们在删除的时候考虑进去就好了，这个并不难解决。下面，我们按照上面的逻辑来把代码写出来~


bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			if (cur->_left == nullptr)
			{
				if (parent->_left == cur)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_right;

				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent->_left == cur)
					parent->_left = cur->_left;
				else
					parent->_right = cur->_left;

				delete cur;
				return true;
			}
			else
			{
				Node* rightMin = cur->_right;
				Node* rightMinParent = nullptr;

				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				//可以交换，也可以直接赋值
				cur->_key = rightMin->_key;

				rigntMinParent->_left = rightMin->_right;

				delete rightMin;
				return true;
			}
		}
	}
	return false;
}

我试着用上述代码把所有插入的结点都删掉，但是程序崩了~有以下几个原因。

在这种情况下，分析删除值为8的节点。该节点的parent为空， 程序执行下面的代码：

if (cur->_left == nullptr)
{
	if (parent->_left == cur)
		parent->_left = cur->_right;
	else
		parent->_right = cur->_right;

	delete cur;
	return true;
}

这时候就是对空指针的解引用了，程序当然会崩掉~所以需要对parent为空的情况单独处理。把上述代码改成这样：

if (cur->_left == nullptr)
{
	  //左为空的情况习下，parent为可能空，即单支的树，所以需要判断
	  if (parent == nullptr)
	  {
		_root = cur->_right;
	  }
	  else
	  {
		if (parent->_left == cur)
			parent->_left = cur->_right;
		else
			parent->_right = cur->_right;
	  }

	  if (parent->_left == cur)
			parent->_left = cur->_right;
		else
			parent->_right = cur->_right;

		delete cur;
		return true;
}

上面分析的是只有左支的情况，只有右支的情况同样如此，需要做单独处理。

解决了只有单支的情况后，我又试着删除所有节点，程序还是崩了~原因如下：

3为要删除的结点。此时，按照代码逻辑，rightMin为6，rightMinParent为空， 后面执行这句代码：

rigntMinParent->_left = rightMin->_right;

 所以会崩掉~但此时我们可以看到，rightMin（节点6）的父亲结点为3，并不是空，所以rightMinParent初始化为空并不合理，应该初始化为cur。

完善到这步，也还有一个小问题，按照上面修改之后的逻辑，rightMin为6，rightMinParent为3，执行这句代码：

rigntMinParent->_left = rightMin->_right;

 我们可以很容易发现这是错的，应该是rightMinParent->_right = rightMin->_right; 所以我们还需要加判断，具体如下：

if (rightMinParent->_left == rightMin)
	rightMinParent->_left = rightMin->_right;
else
	rightMinParent->_right = rightMin->_right;

完整的修改后的代码如下：


bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			if (cur->_left == nullptr)
			{
				//左为空的情况习下，parent为可能空，即单支的树，所以需要判断
				if (parent == nullptr)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}

				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}

				delete cur;
				return true;
			}
			else
			{
				Node* rightMin = cur->_right;
				Node* rightMinParent = cur;

				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				//可以交换，也可以直接赋值
				cur->_key = rightMin->_key;

				//不一定是rigntMinParent的左边
				if (rightMinParent->_left == rightMin)
					rightMinParent->_left = rightMin->_right;
				else
					rightMinParent->_right = rightMin->_right;

				delete rightMin;
				return true;
			}
		}
	}
	return false;
}

二叉搜索树完整代码

#include <iostream>
using namespace std;

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

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

template <class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		Node* newNode = new Node(key);
		_root = newNode;
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	Node* newNode = new Node(key);
	if (parent->_key > key)
		parent->_left = newNode;
	else
		parent->_right = newNode;

	return true;
}

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

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

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					//左为空的情况习下，parent为可能空，即单支的树，所以需要判断
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}

					delete cur;
					return true;
				}
				else
				{
					Node* rightMin = cur->_right;
					//Node* rightMinParent = nullptr;
					Node* rightMinParent = cur;

					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					//不一定是rigntMinParent的左边
					if (rightMinParent->_left == rightMin)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}

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

完~

阅读全部

相关推荐

  3. 数据结构之二叉搜索树

    2024-07-16 23:06:03       49 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-16 23:06:03       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-16 23:06:03       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-16 23:06:03       58 阅读

  19. Python语言-面向对象

    2024-07-16 23:06:03       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-16 23:06:03       64 阅读

热门阅读

  3. Mysql迁移达梦数据库-简介篇

    2024-07-16 23:06:03       18 阅读
  7. ASF平台

    ASF平台

    2024-07-16 23:06:03      20 阅读

  8. 构造器/构造方法

    2024-07-16 23:06:03       19 阅读

  9. Python中的模块和包的定义以及如何在Python中导入和使用它们

    2024-07-16 23:06:03       18 阅读

  16. 数据模型-NoSQL数据模型深入理解

    2024-07-16 23:06:03       20 阅读

  19. 各种常用格式校验方法（身份证号格式校验、手机号格式校验、车牌号格式校验...）正则表达式

    2024-07-16 23:06:03       16 阅读

  21. TCP网络模型

    2024-07-16 23:06:03       20 阅读

  22. 代码随想录算法训练营第35天 | 第九章 动态规划08

    2024-07-16 23:06:03       21 阅读

  23. 使用mediapip 检测pose 并作为一个服务

    2024-07-16 23:06:03       23 阅读

  26. 代码随想录训练营Day 73|dijkstra（堆优化版）精讲、Bellman_ford 算法精讲

    2024-07-16 23:06:03       23 阅读

  28. 计算机图形学题库

    2024-07-16 23:06:03       18 阅读