【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

这篇具有很好参考价值的文章主要介绍了【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言
🍁你好,我是 RO-BERRY
📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言



1. 二叉搜索树概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

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

二叉搜索树(Binary Search Tree,简称BST)是种常用的数据结构,它是一棵二叉树,并且满足以下性质:

对任意节点,其左子树中的节点的值都小于该节点的值。
对于任意节点,其右子树中的所有节点的值都大于该节点的值。
左子树和右子树也都是二叉搜索树。
二叉搜索树的这种特性使得它在查找、插入和删除操作上具有高效性能。通过比较节点的值,可以快速定位到目标节点或者确定插入位置。

二叉搜索树的操作包括:

查找:从根节点开始,递归地比较目标值与当前节点的值,直到找到目标节点或者遍历到叶子节点。
插入:从根节点开始,递归地比较目标值与当前节点的值,根据大小关系选择左子树或右子树进行插入,直到找到合适的插入位置。
删除:删除操作比较复杂,需要考虑被删除节点的子节点情况。可以分为三种情况:被删除节点没有子节点、被删除节点只有一个子节点、被删除节点有两个子节点。
二叉搜索树的时间复杂度取决于树的高度,平均情况下为O(log n),最坏情况下为O(n)。为了保持树的平衡,可以使用平衡二叉搜索树(如AVL树、红黑树)来优化性能。

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言

2. 二叉搜索树操作

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
  1. 二叉搜索树的查找
    a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
    b、最多查找高度次,走到到空,还没找到,这个值不存在。
  2. 二叉搜索树的插入
    插入的具体过程如下:
    a. 树为空,则直接新增节点,赋值给root指针
    b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言

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

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题–替换法删除

【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言

3. 二叉搜索树的实现

3.1 准备工作

结点结构体BSTreeNode

我们实现二叉搜索树需要定义其结点,定义其左右节点以及value,方便后续操作进行

template<class K>
struct BSTreeNode      //二叉树结点
{
	typedef BSTreeNode<K> Node;     //简化名称

	Node* _left;        //左节点
	Node* _right;       //右节点
	K _key;             //结点value

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

二叉搜索树BinarySearchTree

template<class K>
class BinarySearchTree
{
	typedef BSTreeNode<K> Node;    //节点名称简化
public:
	.....         //二叉搜索树函数接口
private:
	Node* _root = nullptr;        //省略了初始化在定义的时候就进行初始化
};

3.2 函数体实现

📖bool Insert(const K& key)

实现思路:

二叉搜索树的定义是左边的子结点必定小于父节点,右边的子结点必定大于父节点,所以我们采取key值与节点value比较,如果key大于节点value,则继续与节点右子节点比较;如果key小于节点value,则继续与节点左子节点比较,最终如果走到空的位置,则进行插入。

这里我们需要定义一个parent节点帮助我们定位最终插入后其父节点的位置,然后将父节点与新插入的结点进行连接,将父节点的value与key值比较,若key大于value,那么肯定是被插入到父节点的右子树里了;若key小于value,则反之。

另:我们要独自判断空树的情况,不然会出现程序崩溃;搜索二叉树的每一个节点数值不能一样,那么我们如果插入的key与某个value相等,也会返回false

实现代码:

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			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 = new Node(key);
		if (parent->_key < key)   //连接父节点
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

📖bool Find(const K& key)

实现思路:

左边的子结点必定小于父节点,右边的子结点必定大于父节点,所以我们采取key值与节点value比较,如果key大于节点value,则继续与节点右子节点比较;如果key小于节点value,则继续与节点左子节点比较,最终如果走到空的位置,则返回false,如果找到与key相等的value,则返回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()

实现思路:

使用递归实现中序遍历,二叉搜索树的中序遍历其实输出出来是一个递增排序的数组,从根节点开始,访问其左子树,并进行打印,然后访问右子树进行打印。
这里用了一个巧妙的方法: 我们对二叉搜索树打印需要传入根节点位置,才能进行递归,但是根节点为私有成员,我们要么写一个GetRoot()函数获取到根节点位置,才能传入,我们在这里可以对其进行封装,在上面重新定义一个打印函数,然后在这个函数里面调用刚刚的打印函数,并传入root,这样就不用在调用的时候传入root了。

实现代码:

	void InOrder()       //巧妙调用输出函数
	{
		_InOrder(_root);
		cout << endl;
	}

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

📖删除 Erase

实现思路:
二叉搜索树(Binary Search Tree,BST)的删除操作是指在BST中删除一个指定的节点。删除操作的模拟实现可以按照以下步骤进行:

首先,需要找到要删除的节点。从根节点开始,比较要删除的节点值与当前节点值的大小关系,如果相等则找到了要删除的节点,如果小于当前节点值,则继续在左子树中查找,如果大于当前节点值,则继续在右子树中查找。重复这个过程直到找到要删除的节点或者遍历到叶子节点为止。

如果找到了要删除的节点,需要考虑以下几种情况:

  1. 如果要删除的节点是叶子节点(没有子节点),直接删除即可。
  2. 如果要删除的节点只有一个子节点,将其子节点替代要删除的节点即可。
  3. 如果要删除的节点有两个子节点,需要找到其右子树中的最小节点(或者左子树中的最大节点),将其值替换到要删除的节点上,并将最小(或最大)节点删除。

实现删除操作时,需要注意维护BST的性质,即左子树中的所有节点值都小于当前节点值,右子树中的所有节点值都大于当前节点值。

实现代码:

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							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)
						{
							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;

					if (rightMin == rightMinParent->_left)     //根节点
						rightMinParent->_left = rightMin->_right;    
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

📖构造函数、析构函数、拷贝构造以及复制拷贝

这里直接实现,不再讲述原理,因为这一块比较基础了

	//强制生成默认构造
	BinarySearchTree() = default;

	BinarySearchTree(const BinarySearchTree<K>& t)   //拷贝构造函数
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return new Root;
	}

	BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)    //赋值拷贝
	{
		swap(_root, t._root);
		return *this;
	}

	~BinarySearchTree()   //析构函数
	{
		Destroy(_root);
	}

3.3 函数体实现(优化版)

我们的优化主要用了封装的艺术

📖优化版insert函数

我们在上面的函数实现时需要判断最终在左子树还是在右子树,并且还要定义一个parent来存储其父节点,而我们对其进行优化,可以看到我们在函数参数里加了一个Node*& root,正是这个参数,我们使用了引用,就不需要再判断其是左子树还是右子树,也不用记录其父节点,因为引用就是别名,我们对其进行修改就是对这个指针进行修改,这里还用了递归,让我们的代码量大大减小

public:
	bool InsertR(const K& key)      //函数放在public便于访问
	{
		return _InsertR(_root, key);
	}
private:                              //函数的具体实现放在private
	bool _InsertR(Node*& root,const K& key)   //这里使用别名,修改的就是其本身,就不用判断左右节点了
	{
		if (root == nullptr)
		{
			root=new Node(key);
			return true;
		}
		if (root->_key < key)                 //小于key就遍历右子树
		{
			return _InsertR(root->_right, key);
	}
		else if (root->_key > key)            //大于key就遍历左子树
		{
			return _InsertR(root->_left, key);  
		}
		else
		{
			return false;
		}
	}

📖优化版find函数

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

📖优化版Erase函数

public:
	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->_right == nullptr)
			{
				root = root->_left;
			}
			else if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else
			{
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMin = rightMin->_left;
				}

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

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

3.4 源代码BinarySearchTree.h

#pragma once

#include<iostream>
using namespace std;
template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	Node* _left;
	Node* _right;
	K _key;

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

template<class K>
class BinarySearchTree
{
	typedef BSTreeNode<K> Node;
public:
	//强制生成默认构造
	BinarySearchTree() = default;

	BinarySearchTree(const BinarySearchTree<K>& t)   //拷贝构造函数
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return new Root;
	}

	BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)    //赋值拷贝
	{
		swap(_root, t._root);
		return *this;
	}

	~BinarySearchTree()   //析构函数
	{
		Destroy(_root);
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			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 = new Node(key);
		if (parent->_key < key)   //连接父节点
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		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;
	}


	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							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)
						{
							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;

					if (rightMin == rightMinParent->_left)     //根节点
						rightMinParent->_left = rightMin->_right;    
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}


	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:

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

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

	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->_right == nullptr)
			{
				root = root->_left;
			}
			else if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else
			{
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMin = rightMin->_left;
				}

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

				return _EraseR(root->_right, 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 = nullptr;
};


4. 二叉搜索树的应用

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

比如:
给一个单词word,判断该单词是否拼写正确,具体方式如下:
以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。

  1. KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:

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

kv二叉树实现

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K, V> Node;

		Node* _left;
		Node* _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:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			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, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			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 (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								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)
							{
								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;

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

						delete rightMin;
						return true;
					}
				}
			}

			return false;
		}

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

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

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

	private:
		Node* _root = nullptr;
	};
}

5. 二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST),c++入门到精通,c++,java,开发语言

  1. 最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为: l o g 2 N log_2 N log2N
  2. 最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为: N 2 \frac{N}{2} 2N

问题:如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插
入关键码,二叉搜索树的性能都能达到最优?那么我们后续章节学习的AVL树和红黑树就可以上
场了。文章来源地址https://www.toymoban.com/news/detail-844105.html

到了这里,关于【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://blog.csdn.net/weixin_60521256/article/details/136896666

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(7)
  • 【C++庖丁解牛】实现string容器的增删查改 | string容器的基本接口使用

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 函数名称 功能说明 push_back 在字符串后尾插字符c append 在字符串后追加一个字符串 operator+= (重点) 在字符

    2024年03月14日
    浏览(9)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(14)
  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(15)
  • 【C++庖丁解牛】STL之vector容器的介绍及使用 | vector迭代器的使用 | vector空间增长问题

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 vector的文档介绍 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存

    2024年03月14日
    浏览(26)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(11)
  • 【C++庖丁解牛】面向对象的三大特性之一多态 | 抽象类 | 多态的原理 | 单继承和多继承关系中的虚函数表

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 需要声明的,本节课件中的代码及解释都是在vs2013下的x86程序中,涉及的指针都是4bytes。如果要其他平台

    2024年04月10日
    浏览(8)
  • 庖丁解牛函数知识---C语言《2》

    目录 前言: 1.嵌套调用函数 2.链式访问 3.函数的声明与定义 4.*递归 5.递归与非递归 ❤博主CSDN:啊苏要学习   ▶专栏分类:C语言◀   C语言的学习,是为我们今后学习其它语言打好基础,C生万物!   开始我们的C语言之旅吧!✈   在第一篇的基础上,我们接着学习函数相关的

    2024年02月02日
    浏览(8)
  • 庖丁解牛函数知识---C语言《1》

    目录 前言: 1.程序中的函数 2.库函数的学习和使用 3.自定义函数 4.传值调用与传址调用 5.形参与实参 6.练习---二分查找函数 ❤博主CSDN:啊苏要学习   ▶专栏分类:C语言◀   C语言的学习,是为我们今后学习其它语言打好基础,C生万物!   开始我们的C语言之旅吧!✈   在计

    2024年02月02日
    浏览(17)
  • 【数据结构】 队列详解!庖丁解牛般细致讲解!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! 什么是队列?队列有什么样的特性?它的应用场景有哪些? 本文会对队列这种数据结构进行进行庖丁解牛般的讲解,让你彻底学会数据结构! 队列是一种常见的数据结构,它按照先进先出

    2024年02月06日
    浏览(10)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包