数据结构---二叉搜索树

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

二叉搜索树

什么是二叉搜索树?

二叉搜索树(Binary Search Tree 简称BST)又称二叉排序树,是一种二叉树的特殊形式,它在每个节点上存储的键值满足以下性质:

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

根据这个性质,我们可以利用二叉搜索树进行高效的插入,删除和搜索操作。

数据结构---二叉搜索树,数据结构,C++,数据结构

二叉搜索树的操作

查找

  • 从根节点开始比较,如果比根节点大则往右查找,反之往左查找。
  • 最多查找高度次,走到空,还没找到,这个值不存在。

上面的图,比如果要查找4.

4 < 8,往左走,找到3,4大于3,往右走,找到6,6大于4,往左走,找到4,4 == 4,查找成功。

重复上面的操作,直到走到4,4小于5,往右走,为nullptr,不存在这个值,返回false。

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

插入

  • 树为空,则直接新增节点,赋值给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;
		}
	}

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

	return true;
}

如果要插入的值(val)比当前节点的key大,则往右子树移动;反之往左子树移动,直到找到合适的插入位置。

在找到插入位置的时候,不要直接 cur = new Node(val),这样创建的是临时变量,出了作用域会销毁,可以用一个临时变量(parent)记录查找过程中cur的上一个位置,在找到合适的位置的时候,与parent节点的key进行比较之后,在进行链接。

删除

删除有点麻烦,

数据结构---二叉搜索树,数据结构,C++,数据结构

看这棵树,把7删了,很简单,delete了就行了,把14给删了呢?右子树的所有节点一定大于根节点,把13链接在10的右子树即可,就算13下面还有子树,也不会导致这个树混乱。那么删3呢?3有两个孩子,这个时候可以找人把3给替代了,从左子树找最大的节点,或者找右子树的最小节点完成替代。

删除分三种情况

  1. 没有孩子
  2. 一个孩子
  3. 两个孩子 (找左子树的最大节点 or 右子树的最小节点)

首先要找到要删除节点的位置(cur),但光找到一个节点的位置不够,还要找到当前节点的父节点(parent)。如果说cur的左子树为空,并且要删除的节点为根节点。

数据结构---二叉搜索树,数据结构,C++,数据结构

也就是当前cur位于8的位置,此时要删除,把根节点移动到cur的右子树位置即可。

若要删的不是根节点。

数据结构---二叉搜索树,数据结构,C++,数据结构

此时cur=6,parent=3,要先判断cur与parent的关系,然后直接将parent与cur的子树链接在一起即可。这是要删除节点的左子树为空的情况,右子树为空与这个一样。


若要删除的节点有两个孩子。

数据结构---二叉搜索树,数据结构,C++,数据结构

要先找到左子树中最大的节点(leftMax),将根节点的key与leftMax的key交换。在找leftMax的过程中记录下来其父节点(parent),判断parent和leftMax的关系。最后将parent与leftMax的左右节点(都为空)链接一下即可。


当然还有一种特殊情况。

数据结构---二叉搜索树,数据结构,C++,数据结构

这里要删除8,而3就是左子树中最大的节点。所以这种情况下的parent初始值不能设为nullptr,而是初始化为cur。leftMax还是初始化为cur->left


		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 (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
				}
				else
				{}
				delete cur;
				return true;
			}
		}

源代码

非递归版

#pragma once


template <class K>
class BSTreeNode
{
public:

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

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

	
};


template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		return true;
	}

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

	bool erase(const K& key)
	{
		Node* parent = _root;
		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 (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
				}
				else
				{
					Node* parent = cur;					
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}
					swap(leftMax->_key, _root->_key);
					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_right;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	Node* _root;
};

递归版文章来源地址https://www.toymoban.com/news/detail-731245.html

#pragma once


template <class K>
class BSTreeNode
{
public:

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

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



};


template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	bool Insert(const K& key)
	{
		return _Insert(_root, key);
	}

	bool Find(const K& key)
	{
		return _Find(_root, key);
	}

	bool erase(const K& key)
	{
		return _erase(_root, key);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	bool _erase(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _erase(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _erase(root->_right,key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* leftMax = root->_left;

				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}

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

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

			delete del;

			return true;
		}

		return false;
	}

	bool _Insert(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

	bool _Find(Node* root, const K& key)
	{
		if (root == nullptr) {
			return false;
		}

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

	Node* _root;
};

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

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

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

相关文章

  • 高级数据结构——二叉搜索树

    目录 1. 二叉搜索树的概念 2. 二叉搜索树的实现 结点类 二叉搜索树的类 2.1 默认成员函数 2.1.1 构造函数 2.1.2 拷贝构造函数 2.1.3 赋值运算符重载函数 2.1.4 析构函数 2.2 中序遍历 2.3 insert插入函数 2.3.1 非递归实现 2.3.2 递归实现 2.4 erase删除函数 2.4.1 非递归实现 2.4.2 递归版本

    2024年02月10日
    浏览(41)
  • 高级数据结构 <二叉搜索树>

    本文已收录至《数据结构(C/C++语言)》专栏! 作者:ARMCSKGT 前面我们学习了二叉树,但仅仅只是简单的二叉树并没有很大的用处,而本节的二叉搜索树是对二叉树的升级,其查找效率相对于简单二叉树来说有一定提升,二叉搜索树是学习AVL树和红黑树的基础,所以我们必须先

    2024年02月04日
    浏览(45)
  • 算法与数据结构--二叉搜索树与自平衡二叉搜索树

    注:字典的 \\\"member运算\\\" 指的是检查字典中是否存在某个特定的键的操作,即查询操作。 如果我们使用数组来实现字典/map,虽然使用二分法查询也可以达到logn,但是的话插入和删除太慢了。使用链表实现的话虽然插入和删除是O(1),但是查询的话达到了O(n),也不可取。 因此人

    2024年02月04日
    浏览(38)
  • 数据结构篇八:二叉搜索树

      前面我们已经学习过了二叉树,二叉搜索树是在二叉树的基础上增添了一些规则,使其能完成快速查找的功能,同时它也帮助我们更好的理解后续将要学习的map和set。   二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为

    2024年03月13日
    浏览(50)
  • 数据结构之二叉搜索树

    满足条件: 1.对于根节点:左子树中所有节点的值小于右子树中所有节点的值 2.任意节点的左右子树也是二叉搜索树,同样满足条件1 我们将二叉搜索树封装为一个类 BinarySearchTree ,并声明一个成员变量 root ,指向树的根节点 查找节点 给定目标值 target ,我们可以根据二叉搜索

    2024年01月20日
    浏览(37)
  • 【数据结构】二叉搜索树BSTree

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 左根右 它的左右子树也分别为二叉搜索树 之所以又叫二叉排

    2024年02月03日
    浏览(44)
  • 数据结构:二叉搜索树(非递归实现)

    目录 1、二叉搜索树 2、二叉搜索树的相关操作。 1、查找 2、插入 3、删除 3、代码实现(非递归) 二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树,其中每个节点的值大于其左子树中所有节点的值,小于其右子树中所有节点的值。这种特性使得二叉搜索树具有快速

    2024年03月08日
    浏览(38)
  • 【数据结构】搜索二叉树(C++实现)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译 二叉搜索树又称二叉排序树,它或者是一棵空

    2024年02月07日
    浏览(52)
  • 数据结构_进阶(1):搜索二叉树

    建议再看这节之前能对C++有一定了解 二叉树在前面C的数据结构阶段时有出过,现在我们对二叉树来学习一些更复杂的类型,也为之后C++学习的 map 和 set 做铺垫 1. map和set特性需要先铺垫二叉搜索树 ,而二叉搜索树也是一种树形结构 2. 二叉搜索树的特性了解,有助于更好的理

    2024年02月16日
    浏览(46)
  • 【数据结构】 二叉搜索树的实现

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 比如以下就为一个人二叉搜

    2024年02月09日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包