【C++】二叉搜索树BST

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

1.二叉搜索树的性质

二叉搜索树又称二叉排序树,具有以下性质:

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

搜索二叉树不允许数据冗余,也就是说其中没有重复的数据

2.二叉搜索树功能的实现

1.二叉搜索树的框架

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

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:

	//功能:插入...
	
private:
	Node* _root = nullptr;
}

2.插入

插入的过程:

  1. 树为空,则直接新增节点,赋值给root指针(所以插入的第一个值就是根)
  2. 树不空,按二叉搜索树性质查找插入位置,插入新节点

注意:二叉搜索树不允许数据冗余,插入相同的数据返回false,用返回值用bool即可。

//插入
bool insert(const K& key)
{
	//空树情况
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;//记录父节点,插入后用以链接插入的数据

	//找到应该插入的叶子结点位置,
	//cur为空时就是该位置的下一个位置(应该插入的位置)
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	//开辟空间初始化要插入的对象
	cur = new Node(key);

	//链接插入的子节点
	if (key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	return true;
}

3.查找

//查找
bool Find(const K& key)
{
	Node* cur = _root;
	
	while (cur)
	{
		if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			cur = cur->left;
		}
		else
		{
			return true;
		}
		
		return false;
	}
}

4.删除(难点)

删除分为三种情况:

  1. 删除节点为叶子结点
    【C++】二叉搜索树BST

  1. 删除节点的左子树为空或右子树为空
    【C++】二叉搜索树BST

  1. 删除节点的左右子树都不为空
    【C++】二叉搜索树BST

因为左子树的最大节点与右子树的最小节点都可以满足二叉搜索树的性质:

  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值

代码实现:

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

	while (cur)
	{
		//查找要删除的节点
		if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			cur = cur->_left;
		}
		else//key == cur->_key找到了 ==> 删除
		{
			//0.要删除的节点左右子树都为空
			if (cur->_left == nullptr && cur->_right == nullptr)
			{
				parent->_left = nullptr;
				parent->_right = nullptr;
				delete cur;
			}
			//1.要删除的节点只有右子树,没有左子树
			else if (cur->_left == nullptr)
			{
				//如果要删除的是根,没有父节点,直接更新_root即可
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left == cur->_right;
					}
					else//parent->_right == cur
					{
						parent->_right == cur->_right;
					}
				}
				delete cur;
			}
			//2.要删除的节点只有左子树,没有右子树
			else if (cur->_right == nullptr)
			{
				//如果要删除的是根,没有父节点,直接更新_root即可
				if (cur == _root)
				{
					_root = cur->_lift;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left == cur->_left;
					}
					else//parent->_right == cur
					{
						parent->_right == cur->_left;
					}
				}
				delete cur;
			}
			//3.要删除节点的左右子树都不为空
			else
			{
				//查找 a 或 b :
				//a.右子树的最小节点-->右子树的最左节点
				//b.左子树的最大节点-->左子树的最右节点

				//查找右子树的最左节点
				Node* Pmin_Right = cur;
				Node* min_Right = cur->_right;

				while (min_Right->_left)
				{
					Pmin_Right = min_Right;
					min_Right = min_Right->_left;
				}

				//将min_Right的值给cur,等于删除了cur,之后释放min_Right即可
				cur->_key = min_Right->_key;

				if (Pmin_Right->_left == min_Right)
				{
					Pmin_Right->_left = min_Right->_right;
				}
				else
				{
					Pmin_Right->_right = min_Right->_right;
				}

				delete min_Right;
			}
		}
	}
}

解析

注意删除节点的时候,都需要记录一下删除节点的父节点,因为需要清除父节点的指针或者需要修改父节点的子树!

1.在树中查找要删除的节点:
【C++】二叉搜索树BST

2.删除要分三种情况:
a.要删除的节点为叶子结点,左右子树都为空:
直接删除即可。
【C++】二叉搜索树BST


b.要删除的节点只有一个子树:
删除后要托孤,将子树给删除节点的父节点。
注意:删除的节点如果是根节点,父节点为nullptr,要特殊处理,要不然会报错!!
【C++】二叉搜索树BST

【C++】二叉搜索树BST
【C++】二叉搜索树BST


c.要删除的节点有两个子树:
删除该节点后,无法托孤给父节点,因为一个节点只能链接两个子节点。
所以要特殊处理:
从该节点的左子树或者右子树中查找一个满足二叉搜索树规则的节点来替换该节点,不就等于删除了该节点吗?
——满足条件的节点:1.左子树的最大节点;2.右子树的最小节点;
那么为什么这两个节点满足条件呢?
——因为这两个节点满足二叉搜索树的规则:左子树的所有节点都小于该节点,右子树的所有节点都大于该节点。
那么这两个节点应该如何找到呢?
——左子树的最小节点:左子树的最靠右一个节点;右子树的最大节点:右子树的最靠左一个节点;

1.这里以右子树的最左节点为例:
(记录其父节点Pmin_Right)
【C++】二叉搜索树BST
2.找到对应的节点以后,对其与要删除的节点进行替换:
注意这里要分两种情况:
注意:min_Right已经是右子树的最左节点了,所以它不可能有左子树,也就是只可能存在min_Right->right

情况一:
这种情况下,Pmin_Right->left == min_Right,可以直接将min_Right->right赋值给Pmin_Right->left。(因为是最左节点,所以只可能是赋值给父节点的左子树)
【C++】二叉搜索树BST

情况二:
这种情况下Pmin_Right->left != min_Right,Pmin_Right->right == min_Right,则要将min_Right->right赋值给Pmin_Right->right。(min_Right不可能有左子树,因为它是最左节点)【C++】二叉搜索树BST
实现:
【C++】二叉搜索树BST

3.二叉搜索树功能的递归实现

1.查找递归实现

//查找递归实现
bool FindR(const K& key)
{
	return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
	if(root == nullptr)
	{
		return false;
	}
	if(root->_key == key)
	{
		return true;
	}
	if(root->_key < key)
	{
		return _FindR(root->_right, key);
	}
	else
	{
		return _FindR(root->_left, key);
	}
}

2.插入递归实现

bool InsertR(const K& key)
{
	return _InsertR(_root, key);
}

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//root->_key == key
	{
		return false;
	}
}

递归形式中新建节点的链接问题

解析:递归形式中链接的问题
在插入递归实现的时候,需要新建立节点然后再链接节点,在传root参数的时候,使用传引用传参,就可以做到自动链接新建的节点。
当我们在当前函数栈帧root = new Node(key)创建新的节点时,因为用了引用,其实这里的root就是上一个函数栈帧中的root->right,所以在创建节点完成,返回的时候就等同于完成了链接,其本质就等同于:root->_right = new Node(key);
【C++】二叉搜索树BST

3.删除的递归实现

//删除递归实现
bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{
	if(root == nullptr)
	{
		return false;
	}
	if(root->_key < key)
	{
		return _EraserR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _EraseR(root->_left, key);
	}
	else//key == _key
	{
		//找到了,开始删除
		Node* del = root;
		if(root->_left == nullptr)
		{
			root = root->_right;
		}
		else if(root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			//左右子树都在,找左子树的最大节点/右子树最小节点
			Node* maxleft = root->_left;
			while(maxfile->_right)
			{
				maxleft = maxleft->_right;
			}
			swap(root->_key, maxleft->_key);
			
			return _EraseR(root->_left, key);
		}
		
		delete del;
		return true;
	}
}

解析:
递归删除与普通删除的实现原理相同:
1.要删除的节点为叶子结点,左右子树都为空;
2.要删除的节点只有一个子树;
3.要删除的节点有两个子树;
三种方式删除后都需要delete释放该节点,所以需要用一个del变量来记录要删除的root指针。(删除后root指针置空找不到了)


1.其中1和2两种方式可以用同一种方式解决:
两种情况可以通过下面一段代码完成:
【C++】二叉搜索树BST

要删除的节点为叶子结点:
因为root->_left == nullptr,则root = root->_right = nullptr,最后delete del后,即删除完成该节点。
【C++】二叉搜索树BST
要删除的节点只有一个子树:
root->_right == nullptr,root = root->_left,直接用其子节点覆盖该节点,最后释放del该节点即可。
【C++】二叉搜索树BST


2.要删除的节点有两个子树:
思路与非递归实现删除的思路相同,寻找左子树的最大节点或右子树的最小节点后进行替换然后删除即可。
进而引入递归的思路:
找到左子树的最大节点(右子树的最小节点)后,将其与要删除的节点进行swap交换key,将删除有两个子树节点的问题转化为删除没有子树节点的问题或只有一个子树节点的问题。
交换完成后再次递归进入左子树重新查找key,找到后直接删除即可(问题3转化为1、2情况来删除)。
【C++】二叉搜索树BST
【C++】二叉搜索树BST


4.二叉搜索树部分默认成员函数实现

1.构造函数

//强制生成默认构造,root声明时候给了缺省值nullptr
BSTree() = default;

解析:
C++11的新特性:default
在函数声明后加=default,将该函数声明为 default 函数,编译器将为显式声明的default函数自动生成函数体。

defaulted函数特性仅适用于类的特殊成员函数,且该特殊成员函数没有默认参数。
defaulted函数既可以在类体里(inline)定义,也可以在类体外定义。

2.拷贝构造函数

//拷贝构造
BSTree(const BSTree<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 newRoot;
}

3.析构函数

//析构(递归)
~BSTree()
{
	Destory(_root);
}

void Destory(Node*& root)
{
	if (root == nullptr)
	{
		return;
	}
	//左-右-根
	Destory(root->_left);
	Destory(root->_right);

	delete root;
	root = nullptr;
}

4.赋值运算符重载

//赋值运算符重载
BSTree<K>& operator=(BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}

5.二叉搜索树实现集合

namespace key
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

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

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		//强制生成默认构造,下面给了缺省值
		BSTree() = default;

		//拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = copy(t._root);
		}

		//赋值运算符重载
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		//析构(递归)
		~BSTree()
		{
			Destory(_root);
		}

		//插入
		bool insert(const K& key)
		{
			//空树情况
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* cur = _root;
			Node* parent = nullptr;//记录父节点,插入后用以链接插入的数据

			//找到应该插入的叶子结点位置,
			//cur为空时就是该位置的下一个位置(应该插入的位置)
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else//二叉搜索树不能有相同的节点
				{
					return false;
				}
			}
			//开辟空间初始化要插入的对象
			cur = new Node(key);

			//链接插入的子节点
			if (key > parent->_key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}


		//查找
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					cur = cur->left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

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

			while (cur)
			{
				//查找要删除的节点
				if (key > cur->_key)
				{
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					cur = cur->_left;
				}
				else//key == cur->_key找到了 ==> 删除
				{
					//0.要删除的节点左右子树都为空
					if (cur->_left == nullptr && cur->_right == nullptr)
					{
						parent->_left = nullptr;
						parent->_right = nullptr;
						delete cur;
					}
					//1.要删除的节点只有右子树,没有左子树
					else if (cur->_left == nullptr)
					{
						//如果要删除的是根,没有父节点,直接更新_root即可
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left == cur->_right;
							}
							else//parent->_right == cur
							{
								parent->_right == cur->_right;
							}
						}
						delete cur;
					}
					//2.要删除的节点只有左子树,没有右子树
					else if (cur->_right == nullptr)
					{
						//如果要删除的是根,没有父节点,直接更新_root即可
						if (cur == _root)
						{
							_root = cur->_lift;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left == cur->_left;
							}
							else//parent->_right == cur
							{
								parent->_right == cur->_left;
							}
						}
						delete cur;
					}
					//3.要删除节点的左右子树都不为空
					else
					{
						//查找 a 或 b :
						//a.右子树的最小节点-->右子树的最左节点
						//b.左子树的最大节点-->左子树的最右节点

						//查找右子树的最左节点
						Node* Pmin_Right = cur;
						Node* min_Right = cur->_right;

						while (min_Right->_left)
						{
							Pmin_Right = min_Right;
							min_Right = min_Right->_left;
						}

						//将min_Right的值给cur,等于删除了cur,之后释放min_Right即可
						cur->_key = min_Right->_key;

						if (Pmin_Right->_left == min_Right)
						{
							Pmin_Right->_left = min_Right->_right;
						}
						else
						{
							Pmin_Right->_right = min_Right->_right;
						}

						delete min_Right;
					}
				}
			}
		}

		//中序遍历
		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);
		}

	protected:
		//拷贝构造
		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 newRoot;

		}

		//析构
		void Destory(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			//左-右-根
			Destory(root->_left);
			Destory(root->_right);

			delete root;
			root = nullptr;
		}

		//中序遍历
		void _InOrder(Node* root)//1.缺省值必须是全局变量或者常量2.访问root需要this指针,this指针也是另一个参数,这里不一定能用
		{
			if (root == nullptr)
			{
				return;
			}

			//左->根->右
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

		//查找递归实现
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (root->_key == key)
			{
				return true;
			}

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else
			{
				return _FindR(root->_left, key);
			}
		}

		//插入递归实现
		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//root->_key == key
			{
				return false;
			}
		}

		//删除递归实现
		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//key == _key
			{
				//开始删除
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* maxleft = root->_left;
					while (maxleft->_right)
					{
						maxleft = maxleft->_right;
					}

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

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

				delete del;
				return true;
			}

		}

	private:
		Node* _root = nullptr;
	};
}

5.二叉搜索树增删查改的时间复杂度

时间复杂度为:
O(logN)~O(N)
最优情况下,接近或就是完全二叉树,时间复杂度为O(logN)。
最坏情况下二叉搜索树可能会出现单支树,此时为O(N)。
对二叉搜索树进行优化,控制左右子树的平衡就有了:AVL树和红黑树。
(AVL树与红黑树后续学习)

6.二叉搜索树的应用

K模型(key)

应用于搜索场景:在不在的问题。

结构体中只存在关键码key,关键码就是所需要查找的值。

比如:检查单词是否拼写正确,将词库中的每个单词都作为key构建二叉搜索树,进而检索单词查看是否拼写正确。

KV模型(key-value)

应用于搜索场景:通过一个值查找另一个值的问题。

**每个关键码key,都有与之对应的值value,结构中存在<key, value>的键值对。**通过key来查找value。

比如:中英互译的字典<english, chinese>,就是一对键值对;
或者可以统计单词出现的次数<word, count>,也是一对键值对;

(我们上面实现的是key模型的二叉搜索树)文章来源地址https://www.toymoban.com/news/detail-424610.html

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

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

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

相关文章

  • 二叉搜索树(BST)详解

    二叉搜索树是一个有序树 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 左、右子树也分别为二叉搜索树; 如图所示,两棵都是二叉排序树; 如图所示,左右两棵树都是是二叉搜

    2024年02月02日
    浏览(40)
  • Java之二叉搜索树(BST)

    目录 一.二叉搜索树(BST) 1.什么是二叉搜索树 2.判断一颗二叉搜索树 二.二叉搜索树CRUD操作 1.二叉搜索树的数据结构 2.添加操作 3.查找操作 1.查找最大值 2.查找最小值 3.查找任意值 4.删除操作 1.删除最大值 2.删除最小值 3.删除任意值 5.其他操作 1.打印操作(toString的实现) 6.代码

    2023年04月25日
    浏览(40)
  • 【开卷数据结构 】二叉排序树(BST)

    目录 二叉排序树(BST) 二叉排序树的定义 二叉排序树的操作 二叉排序树的查找 代码演示 二叉排序树的插入 代码演示 二叉排序树的构造 代码演示 二叉排序树的删除 Q:什么是二叉排序树 A: 二叉排序树或者是一棵空树,或者是具有如下性质的二叉树 1) 若它的左子树不空

    2024年02月11日
    浏览(41)
  • 【数据结构】二叉搜索树BST的实现(递归)

    目录 1.概念 2.图解: 3.元素插入操作 1.思路分析: 2.代码展示: 4.元素查找操作 1.前提根节点不为空 2.代码展示: 5.查找BST中的最大最小值 代码展示: 6.删除BST中的最大最小值 代码展示: 7.删除BST中的任意元素 代码展示:   二叉搜索树又称二叉排序树,它或者是一棵空树,

    2023年04月09日
    浏览(33)
  • 二叉搜索树(Binary Search Tree,BST)

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

    2024年02月09日
    浏览(43)
  • 二叉排序树(BST)创建详解之C语言版

    二叉排序树(Binary Sort Tree或 Binary Search Tree)又称二叉查找树,可以用来实现数据的快速查找,也方便数据的插入、删除等工作,因此适用于数据的动态查找。 二叉排序树是一棵二叉树,其左子树上的元素都小于树根,右子树上的元素都大于树根,所有的子树也满足这个性质

    2024年02月07日
    浏览(31)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 二叉搜索树(二叉排序树)

    二叉搜索树也叫搜索二叉树、二叉排序树、排序二叉树。是一种对查找和排序都有用的特殊二叉树。 二叉搜索树(Binary Search Tree,简称BST) 如何构建一颗二叉搜索树 假设我们有如下数据,我们按从左往右的顺序构建一颗二叉搜索树 1.首先,将8作为根节点 2.插入3,由于3小于

    2024年02月15日
    浏览(27)
  • 二叉排序树(二叉查找树、二叉搜索树)(图解+完整代码)

    目录 ⚽1.什么是二叉排序树 🏐2.构建二叉排序树 🏀3.二叉排序树的查找操作 🥎4.二叉排序树的删除 🎱5.完整代码 我们直接看它的性质: 若它的左子树不空,则左子树上所有结点的值均小于它根结点的值。 若它的右子树不空,则右子树上所有结点的值均大于它根结点的值。

    2024年02月03日
    浏览(33)
  • 【C++】搜索二叉树

    搜索二叉树是一种二叉树,其中每个节点的左子节点的值都小于该节点的值,而右子节点的值都大于该节点的值。这种性质使得在BST中进行搜索、插入和删除操作的平均时间复杂度为 O(log n) ,其中 n 是树中节点的数量。 例子: 在定义和表示二叉搜索树(BST)的节点结构时,

    2024年02月12日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包