• C++进阶：二叉搜索树介绍、模拟实现（递归迭代两版本）及其应用

    上次介绍完多态后：C++进阶：详解多态（多态、虚函数、抽象类以及虚函数原理详解）

    也是要开始继续学习了

    文章目录

    1.二叉搜索树

    1.1概念

    二叉搜索树（Binary Search Tree，BST）是一种二叉树，其中每个节点都具有以下性质：

    • 节点的左子树中的所有节点的值都小于该节点的值。
    • 节点的右子树中的所有节点的值都大于该节点的值。
    • 左右子树也分别为二叉搜索树。

    假设我们插入以下元素：5, 3, 7, 1, 4, 6, 8，可以构建如下的二叉搜索树（BST）：

          5
     / \
    3   7
   / \ / \
  1  4 6  8

    • 1
    • 2
    • 3
    • 4
    • 5

    1.2二叉搜索树特性

    • 中序遍历二叉搜索树得到的序列是有序的。
    • 查找、插入和删除操作的平均时间复杂度为O(log N)，其中N为树中节点的数量

    1.3 二叉搜索树的操作

    1. 插入操作

      • 树为空，则直接新增节点，赋值给root指针

      • 树不空，按二叉搜索树性质查找插入位置，插入新节点

    2. 删除操作

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

      • 如果要删除的节点没有孩子结点，那么可以直接删除它。

      • 如果要删除的节点只有左孩子结点，可以直接删除该节点，并使其父节点指向其左孩子。

      • 如果要删除的节点只有右孩子结点，同样可以直接删除该节点，并使其父节点指向其右孩子。

      • 如果要删除的节点有左、右孩子结点，可以在其右子树中找到中序遍历下的第一个结点（右子树里最小），将其值替换到要删除的节点中，再递归删除右子树中的那个中序遍历下的第一个结点。（这个可以直接删）

    2.模拟实现

    2.1项目文件规划

    在这里插入图片描述

    头文件BSTree.h：进行模拟的编写

    源文件test.cpp：进行测试，检查代码逻辑是否满足期望

    2.2基本结构

    namespace key
{
	template
	struct BSTreeNode
	{
		BSTreeNode* _left;//左指针
		BSTreeNode* _right;//右指针
		K _key;//存数据的

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

	template
	class BSTree
	{
		typedef BSTreeNode Node;
	public:
		BSTree() = default;//强制生成默认构造函数

		BSTree(const BSTree& t)//拷贝构造函数
		{
			//....
		}

		~BSTree()//析构函数
		{
			//...
		}

	private:
		Node* _root = nullptr;//头结点
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    2.3各种接口、功能、以及基本结构的补充

    2.3.1 Find() 查找 （迭代/循环版本）

    		bool 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 true;//这是找到啦
				}
			}
			return false;//没找到才会出循环
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    这里的思路很简单：该key< cur的_key，就进入到左子树；反之进入右子树

    2.3.2 Insert() 插入（迭代/循环版本）

    bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
                return true;
			}
			else
			{
				Node* cur = _root;
				Node* parent = nullptr;//这里存父亲节点，方便后续链接上
				while (cur)
				{
					if (key < cur->_key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else if (key > cur->_key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else
					{
						return false;//搜索二叉树里不能有相同 
					}
				}//出来后cur是nullptr,parent是叶子节点
				cur = new Node(key);//重新利用
				if (parent->_key < key)
				{
					parent->_right = cur;
				}
				else
				{
					parent->_left = cur;
				}

				return true;
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    1. 如果二叉搜索树为空（即 _root == nullptr），则创建一个新节点 _root，其键值为 key，并将其作为根节点。
    2. 如果二叉搜索树不为空，则从根节点开始，沿着树的路径向下搜索应该插入新节点的位置。
    3. 在搜索过程中，如果发现要插入的键值 key 小于当前节点的键值，则继续在当前节点的左子树中搜索；如果大于当前节点的键值，则继续在右子树中搜索。
    4. 如果搜索到某个节点的键值与要插入的键值相等，则说明二叉搜索树中不能有相同的节点，直接返回 false。
    5. 当搜索到空节点时，表示找到了要插入新节点的位置，此时创建一个新节点 cur，其键值为 key。
    6. 最后，将新节点 cur 插入到父节点 parent 的左子树或右子树上，具体取决于新节点的键值与父节点的键值的大小关系
    写出中序遍历来进行验证（中序遍历有序）
    void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    这里因为要传入根节点，所以正常无法在外部调用。我们采用子函数的方式来解决这个问题。

    顺便把子函数放在private里，这样更安全

    #include
using namespace std;

#include"BSTree.h"

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    在这里插入图片描述

    2.3.3 Erase() 删除（迭代/循环版本）

    		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)//先找到在哪里删除
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else//进来就说明找到啦，就是现在的cur
				{
					if (cur->_left == nullptr)//左为空，就把右给父亲节点（为空也无妨）
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)//cur在parent右，那就接到右侧
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}

						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)//cur在parent右，那就接到右侧
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					else//左右都不是空，使用替换法，这里用右子树最小来换
					{
						Node* rightMinParent = cur;//右子树最小的父亲节点
						Node* rightMin = cur->_right;//右子树最小的节点

						while (rightMin->_left)//开始找
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;//把值一给，现在删rightMin就行了

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

						delete rightMin;
						return true;
					}
				}
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    1. 首先，定义了两个指针 parent 和 cur，分别用来记录当前节点的父节点和当前节点，初始时 cur 指向根节点 _root。
    2. 在 while 循环中，不断遍历二叉搜索树，直到找到要删除的节点或遍历完整棵树。
    3. 在循环中，通过比较要删除的键值 key 与当前节点的键值 cur->_key 的大小关系，来确定是向左子树还是右子树继续遍历。
    4. 如果找到了要删除的节点，根据不同情况进行处理：
    • 如果要删除的节点没有左子树，直接将其右子树接到父节点的相应位置，然后删除该节点。
    • 如果要删除的节点没有右子树，类似地将其左子树接到父节点的相应位置，然后删除该节点。
    • 如果要删除的节点既有左子树又有右子树，采用替换法，找到右子树中最小的节点（即右子树中最左边的节点），将其键值替换到要删除的节点上，然后删除右子树中最小的节点。
    1. 删除节点后，返回 true 表示删除成功
    验证
    int main()
{
	key::BSTree t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Erase(8);
	t.InOrder();

	t.Erase(14);
	t.InOrder();

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

	t.Erase(6);
	t.InOrder();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述

    2.3.4FindR() 查找 （递归版本）

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    1. FindR 函数是对外提供的接口函数，用于从根节点开始递归查找指定键值的节点。
    2. 在 _FindR 函数中，首先判断当前节点是否为空，如果为空则表示在当前路径上没有找到指定键值的节点，返回 false。
    3. 如果当前节点的键值小于要查找的键值 key，则递归调用 _FindR 函数查找右子树。
    4. 如果当前节点的键值大于要查找的键值 key，则递归调用 _FindR 函数查找左子树。
    5. 如果当前节点的键值等于要查找的键值 key，则表示找到了目标节点，返回 true。
    6. 通过递归的方式不断在左右子树中查找，直到找到目标节点或者遍历完整棵树

    2.3.5Insert() 插入 （递归版本）

    bool InsertR(const K& key)//难点在于，如何与父亲节点进行链接
		{
			return _InsertR(_root, key);
		}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    1. InsertR 函数是对外提供的接口函数，用于从根节点开始递归插入新节点。
    2. 在 _InsertR 函数中，参数 root 是一个指向节点指针的引用，这样可以在递归过程中改变节点指针的指向，从而实现与父节点的链接。
    3. 首先判断当前节点是否为空，如果为空则表示可以在该位置插入新节点，创建一个新节点并将其指针赋给 root，然后返回 true。
    4. 如果当前节点的键值小于要插入的键值 key，则递归调用 _InsertR 函数插入到右子树。
    5. 如果当前节点的键值大于要插入的键值 key，则递归调用 _InsertR 函数插入到左子树。
    6. 如果当前节点的键值等于要插入的键值 key，则表示树中已经存在相同键值的节点，返回 false。
    7. 通过递归的方式在左右子树中寻找合适的插入位置，并不断更新父节点的指针，直到插入新节点或者确认新节点已存在

    2.3.6 EraseR() 删除 （迭代版本）

    		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;//保存一下，过会要delete的

				//这里便是引用开始发挥的作用，可以直接进行链接
				if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else//还是使用替换法，不过这次，直接交换后，再去右子树里递归
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
					{
						rightMin = rightMin->_left;
					}

					std::swap(root->_key, rightMin->_key);

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

				delete del;
				return true;
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    1. EraseR 函数是对外提供的接口函数，用于从根节点开始递归删除指定键值的节点。
    2. 在 _EraseR 函数中，参数 root 是一个指向节点指针的引用，这样可以在递归过程中改变节点指针的指向，从而实现删除操作。
    3. 首先判断当前节点是否为空，如果为空则表示在当前路径上没有找到指定键值的节点，返回 false。
    4. 如果当前节点的键值小于要删除的键值 key，则递归调用 _EraseR 函数在右子树中删除。
    5. 如果当前节点的键值大于要删除的键值 key，则递归调用 _EraseR 函数在左子树中删除。
    6. 如果当前节点的键值等于要删除的键值 key，则表示找到了目标节点，进行删除操作。
    7. 如果目标节点只有一个子节点或者没有子节点，直接用子节点替换目标节点即可。
    8. 如果目标节点有两个子节点，找到右子树中最小的节点（即右子树中最左边的节点），将其键值与目标节点键值交换，然后在右子树中递归删除这个最小节点。
    9. 最后删除目标节点，并返回 true 表示删除成功

    2.3.7 补全拷贝构造函数

    		BSTree(const BSTree& t)//拷贝构造函数
		{
			_root = copy(_root);
		}

		Node* copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* newnode = new Node(root->_key);
			if (root->_left)
			{
				newnode->_left = copy(root->_left);
			}
			if (root->_right)
			{
				newnode->_right = copy(root->_right);
			}
			return newnode;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    1. 在拷贝构造函数 BSTree(const BSTree& t) 中，调用了 copy 函数来复制传入二叉搜索树 t 的根节点及其所有子节点。
    2. copy 函数接收一个节点指针 root，用于递归复制以该节点为根的子树。
    3. 首先判断当前节点是否为空，如果为空则返回 nullptr。
    4. 创建一个新节点 newnode，键值为当前节点 root 的键值，表示复制当前节点。
    5. 如果当前节点有左子节点，则递归复制左子树，并将复制得到的左子树根节点赋值给新节点的左指针 _left。
    6. 如果当前节点有右子节点，则递归复制右子树，并将复制得到的右子树根节点赋值给新节点的右指针 _right。
    7. 返回新节点 newnode，表示复制当前节点及其所有子节点。（也是起到链接的作用）
    8. 在拷贝构造函数中，调用 copy 函数复制传入二叉搜索树的根节点，从而完成整棵树的复制。

    2.3.8 补全析构函数

    		~BSTree()//析构函数
		{
			Destory(_root);
		}

		void Destory(Node* root)//走个后序
		{
			if (root == nullptr)
				return;

			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    3.二叉搜索树应用

    1. K模型：

      • 结构：在K模型中，每个节点只包含一个关键码（key），不包含值。节点的左子树中的所有节点都小于当前节点的关键码，右子树中的所有节点都大于当前节点的关键码。
      • 操作：
        • 插入：将新的关键码插入到二叉搜索树中的合适位置，保持树的有序性。
        • 搜索：通过比较关键码，可以快速判断给定的值是否在树中存在。
      • 应用场景：适用于需要快速判断特定值是否存在的场景，如拼写检查、查找特定单词等。

    2. KV模型：

      • 结构：在KV模型中，每个节点包含一个键值对（），其中Key为关键码，Value为对应的值。节点的左子树中的所有节点的关键码小于当前节点的关键码，右子树中的所有节点的关键码大于当前节点的关键码。
      • 操作：
        • 插入：插入新的键值对到二叉搜索树中，保持树的有序性。
        • 搜索：通过比较关键码，可以快速查找对应的值。
      • 应用场景：
        • 英汉词典：以英文单词为关键码，对应的中文翻译为值，可以通过英文单词快速查找对应的中文翻译。
        • 统计单词次数：以单词为关键码，出现次数为值，可以方便地查找给定单词的出现次数。

    4.性能分析

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

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

    在这里插入图片描述

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

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

    为了改进这种情况，可以使用自平衡二叉搜索树，如AVL树和红黑树。这些树在插入和删除操作时会通过旋转和重新平衡操作来保持树的平衡，从而确保树的高度较低，提高了搜索效率。

    我后面也会继续学习，分享给大家！！！

  • 相关阅读:
    码蹄集 - MT2065 - 整数大小比较
    【FPGA教程案例77】通信案例3——数据组帧，帧同步、拆帧
    Java项目：SSM社区居民户籍扶贫管理系统
    2013年武汉某校848数据结构真题
    Hadoop基础入门
    《CTF攻防世界web题》之茶壶我爱你（2）
    通过内网穿透远程控制家中Home Assistant智能家居系统
    C语言-静态通讯录(全功能)(详略版)
    线段树
    MybatisPlus（5）
  • 原文地址：https://blog.csdn.net/qq_74415153/article/details/136882131