1. Toy模板网首页
  2. > Toy博客

C++------利用C++实现二叉搜索树【数据结构】

9月前 作者：ljp_nan 分类：Toy博客 阅读(40) 违法举报

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

二叉搜索树

概念

什么是二叉搜索树，二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构
上面的就是一棵二叉搜索树，我们还可以发现这棵树走一个中序遍历序列是有序的，所以它又被称为二叉排序树。

二叉搜索树的操作

二叉搜索树的操作主要分为以下几点，查找， 插入，删除。

查找

算法思想：二叉搜索树的查找算法是这样的，从根的地方开始找，如果要找的key比根大就到右子树去找，如果比根小就到左子树找。时间复杂度最差为O(N)最优为O(logn)，如果一棵树走完了还没有找到说明这个数字不在这棵树内。
O(N)时间复杂度是下面这棵树的查找产生的。
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构
我们要使树的高度保持为logN就必须引入平衡二叉搜索树的概念，这个部分我们在后面的AVL和红黑树部分讲解。
非递归算法：

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

递归算法：
key小于就递归找左树，大于就递归找右树

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

插入

插入分为两种情况：
1、如果树为空，则直接新增节点，赋值给_root指针。
2、树不为空，按二叉搜索树性质查找插入位置，插入新节点。
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构
非递归算法

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 _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else
			{
				return false;
			}
		}

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：
a.要删除的节点无孩子节点
b.要删除的节点只有左孩子节点
c.要删除的节点只有右孩子节点
d.要删除的节点有左右孩子节点
情况b，c可以合成一个情况，那就是只有一个孩子节点。
情况b：删除该节点且是被删除节点的双亲节点指向被删除节点的左孩子节点—直接删除
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构

情况c：删除该节点且是被删除节点的双亲节点指向被删除节点的右孩子节点—直接删除
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构

情况d：在它的左子树中寻找最大节点，用它的值填补到被删除节点中，再来处理该节点的删除问题—替换法删除。
C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构
非递归算法：

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

			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				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 = _root->_left;
						while (leftmax->_right != nullptr)
						{
							parent = leftmax;
							leftmax = leftmax->_right;
						}

						swap(cur->_key, leftmax->_key);

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

非递归算法：

//Node*& 引用是关键，没有引用就不会链接起来，不用引用也可以用二级指针。
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;
				//1、左为空
				//2、右为空
				//3、左右都不为空

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

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

完整代码

namespace name
{
	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()
			:_root(nullptr)
		{}
		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;
			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 != nullptr)
			{
				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* cur = _root;
			Node* parent = nullptr;

			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				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 = _root->_left;
						while (leftmax->_right != nullptr)
						{
							parent = leftmax;
							leftmax = leftmax->_right;
						}

						swap(cur->_key, leftmax->_key);

						if (parent->_left == leftmax)
						{
							parent->_left = leftmax->_left;
						}
						else
						{
							parent->_right = leftmax->_left;
						}
						cur = leftmax;
					}
					delete cur;
					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 Destory(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			Destory(root->_left);
			Destory(root->_right);
			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else
			{
				return false;
			}
		}
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
			{
				_FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				_FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}
		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;
				//1、左为空
				//2、右为空
				//3、左右都不为空

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}
				delete del;
				return true;
			}
		}
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << " ";
			_Inorder(root->_right);
		}
		Node* _root;
	};
}

二叉搜索树的应用

应用主要是分为了K模型和KV模型，后面的set为K模型，map为KV模型，具体是这样的：

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word,chinese>就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word,count>就构成一种键值对。
    上面的代码时K模型的，下面的代码时KV模型的。
namespace name1
{
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _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:
		//构造函数
		BSTree()
			:_root(nullptr)
		{}
		BSTree(const BSTree<K,V>& t)
		{
			_root = Copy(t._root);
		}
		BSTree<K,V>& operator=(BSTree<K,V> t)
		{
			swap(_root, t._root);
			return *this;
		}
		~BSTree()
		{
			Destory(_root);
		}
		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root,key);
		}
		bool InsertR(const K& key,const V& value)
		{
			return _InsertR(_root, key,value);
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
	private:
		void Destory(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			Destory(root->_left);
			Destory(root->_right);
			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}
		bool _InsertR(Node*& root,const K& key,const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key,value);
				return true;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key, value);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key, value);
			}
			else
			{
				return false;
			}
		}
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return 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;
				//1、左为空
				//2、右为空
				//3、左右都不为空
				
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}
				delete del;
				return true;
			}
		}
		void _Inorder(Node* root)
		{
			if (root==nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_Inorder(root->_right);
		}
		Node* _root;
	};
}

KV模型的测试：

void Test_BSTree7()
{
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	name1::BSTree<string, int> countTree;
	for (auto& str : arr)
	{
		//没有找到证明是第一次出现
		auto ret = countTree.FindR(str);
		if (ret == nullptr)
		{
			countTree.InsertR(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.Inorder();
}
int main()
{
	//Test_BSTree();
	//Test_BSTree1();
	//Test_BSTree2();
	//Test_BSTree3();
	//Test_BSTree4();
	//Test_BSTree5();
	//Test_BSTree6();
	Test_BSTree7();
	return 0;
}

C++------利用C++实现二叉搜索树【数据结构】,C++,数据结构,c++,数据结构
好的我们下一篇再见！文章来源地址https://www.toymoban.com/news/detail-667417.html

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • [数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

    [数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

    二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 我们先给出两个示例： 此

    2024年02月04日
    浏览(42)
  • C++数据结构之平衡二叉搜索树（一）——AVL的实现（zig与zag/左右双旋/3+4重构）

    C++数据结构之平衡二叉搜索树（一）——AVL的实现（zig与zag/左右双旋/3+4重构）

    本文是介绍众多平衡二叉搜索树（BBST）的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树（BST）在极度退化的情况下，十分不平衡，不平衡到只朝一侧偏，成为一条链表，复杂度可达 O ( n ) O(n) O ( n ) ，所以我们要在“平衡”方面做一些约束，以防

    2024年02月13日
    浏览(38)
  • 【C++＆数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现＆逐过程分析＆代码演示&简练易懂]（23）

    【C++＆数据结构】超详细一文带小白轻松全面理解 [ 二叉搜索树 ]—— [从零实现＆逐过程分析＆代码演示&简练易懂]（23）

    前言 大家好吖，欢迎来到 YY 滴数据结构系列 ，热烈欢迎！ 本章主要内容面向接触过C++的老铁 主要内容含： 欢迎订阅 YY 滴C++专栏！更多干货持续更新！以下是传送门！ YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《初

    2024年02月05日
    浏览(114)
  • 【数据结构（C++）】树型查找——二叉搜索树

    【数据结构（C++）】树型查找——二叉搜索树

    目录 1. 二叉搜索树 1.1 二叉搜索树的概念 1.2 二叉搜索树类模板 1.3 二叉搜索树的操作 1.3.1 查找 1.3.2 插入 1.3.3 删除 1.4 二叉搜索树的性能分析 2. 平衡二叉树 2.1 平衡二叉树的概念 2.2 平衡二叉树类模板 2.3 二叉搜索树的插入 3. 红黑树 3.1 红黑树的概念 3.2 红黑树类模板 二叉搜索

    2024年02月10日
    浏览(43)
  • 数据结构：二叉搜索树（非递归实现）

    数据结构：二叉搜索树（非递归实现）

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

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

    【数据结构】 二叉搜索树的实现

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

    2024年02月09日
    浏览(38)
  • 【Java 数据结构】实现一个二叉搜索树

    【Java 数据结构】实现一个二叉搜索树

    目录   1、认识二叉搜索树 2、实现一个二叉搜索树 2.1 成员变量 2.2 insert 方法 2.3 search 方法  2.4 remove 方法(重点) 3、二叉搜索树总结 从字面上来看，它只比二叉树多了搜索两个字，我们回想一下，如果要是在二叉树中查找一个元素的话，需要遍历这棵树，效率很慢，而二叉搜

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

    【数据结构】二叉搜索树BST的实现（递归）

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

    2023年04月09日
    浏览(35)
  • 【数据结构】二叉搜索树——二叉搜索树的概念和介绍、二叉搜索树的简单实现、二叉搜索树的增删查改

    【数据结构】二叉搜索树——二叉搜索树的概念和介绍、二叉搜索树的简单实现、二叉搜索树的增删查改

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

    2024年02月09日
    浏览(39)
  • Java 数据结构篇-实现二叉搜索树的核心方法

    Java 数据结构篇-实现二叉搜索树的核心方法

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 二叉搜索树的概述         2.0 二叉搜索树的成员变量及其构造方法         3.0 实现二叉树的核心接口         3.1 实现二叉搜索树 - 获取值 get(int key)         3.2 实现二叉搜索树

    2024年02月04日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包