您现在的位置是:首页 > 正文

二叉搜索树

2024-04-01 00:01:26阅读 3

二叉搜索树

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

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

在这里插入图片描述

实现二叉搜索树

二叉搜索树结构

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;
	//.....成员函数
private:
	Node* _root = nullptr;
};

插入

循环实现

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

递归实现

通过root的引用可以解决:需要找到父节点才能插入的情况
引用不能改变指向,所以用循环的插入不能用引用

public:
	bool InsertR(const K& key)
	{
		return _InsertR(_root,key);
	}
protected:
	bool _InsertR(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key < root->_key)
			return _InsertR(root->_left, key);
		else if (key > root->_key)
			return _InsertR(root->_right, key);
		else
			return false;
	}

删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

  • 情况b:删除该结点且使被删除节点的父结点指向被删除结点的左孩子结点–直接删除
  • 情况c:删除该结点且使被删除节点的父结点指向被删除结点的右孩子结点–直接删除
  • 情况d:
    替换法
    1.找到左子树的最大(最右)结点,进行交换
    2.找到右子树的最小(最左)结点,进行交换
    交换之后找到要删除结点的父节点链接上要删除结点的孩子结点

循环实现

bool Erase(const K& key)
{
	//要删除的节点有三种情况
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//准备删除
			if (cur->_left == nullptr)//只有右孩子
			{
				if (cur == _root)//如果碰到删最后几个节点的情况
				{
					_root = cur->_right;//更新新的根
					//如果只有最后一个节点,_root变成nullptr,然后cur被delete
				}
				else
				{
					//判断一下parent用left还是right去链接cur的孩子
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else if (cur == parent->_right)
					{
						parent->_right = cur->_right;
					}
					else
					{
						cout << "quit" << endl;
						return 0;
					}
				}
				delete cur;
			}
			
			else if (cur->_right == nullptr)//只有左孩子
			{
				if (cur == _root)//如果碰到删最后几个节点的情况
				{
					_root = cur->_left;//更新新的根
					//如果只有最后一个节点,_root变成nullptr,然后cur被delete
				}
				else
				{
					//判断一下parent用left还是right去链接cur的孩子
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						cout << "quit" << endl;
						return 0;
					}
				}
				delete cur;
			}

			else//左右都有孩子,替换法
			{
				//通过中序找右树中的最小节点
				Node* t = cur->_right;
				Node* parent = cur;//记录t的父节点
				while (t->_left)
				{
					parent = t;
					t = t->_left;
				}
				swap(cur->_key, t->_key);
				//交换后看t是parent的左还是右
				if (t == parent->_left)
				{
					//t已经是最左,所以只可能有右孩子
					parent->_left = t->_right;
				}
				else if (t == parent->_right)
				{
					parent->_right = t->_right;
				}
				else
				{
					cout << "quit" << endl;
					return 0;
				}
				delete t;
			}
			return true;
		}
	}
	return false;
}

递归实现

public:
	bool EraseR(const K& key)
	{
		return _EraseR(_root,key);
	}
protected:
	bool _EraseR(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (key < root->_key)
		{
			return _EraseR(root->_left, key);
		}
		else if (key > root->_key)
		{
			return _EraseR(root->_right, key);
		}
		else
		{
			if (root->_left == nullptr)//只有右孩子
			{
				Node* t = root;
				root = root->_right;
				delete t;
				return true;
			}
			else if (root->_right == nullptr)//只有左孩子
			{
				Node* t = root;
				root = root->_left;
				delete t;
				return true;
			}
			else
			{
				//和右树的最小节点替换,也就是右树的最左
				Node* t = root->_right;
				while (t->_left)
				{
					t = t->_left;
				}
				swap(root->_key, t->_key);
				//交换之后从头找是找不到的,但可以在右树找,然后再删除
				return _EraseR(root->_right, key);
			}
		}
	}

查找

循环实现

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

递归实现

public:
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
protected:
	bool _FindR(Node* root,const K& key)
	{
		if (root == nullptr)
			return false;

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

完整代码

#pragma once
#include<iostream>
using namespace std;

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;
	}
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = cur;
		while (cur)
		{
			parent = cur;
			if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		Node* newnode = new Node(key);
		if (key > parent->_key)
		{
			parent->_right = newnode;
		}
		else
		{
			parent->_left = newnode;
		}
		return true;
	}
	bool Erase(const K& key)
	{
		//要删除的节点有三种情况
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//准备删除
				if (cur->_left == nullptr)//只有右孩子
				{
					if (cur == _root)//如果碰到删最后几个节点的情况
					{
						_root = cur->_right;//更新新的根
						//如果只有最后一个节点,_root变成nullptr,然后cur被delete
					}
					else
					{
						//判断一下parent用left还是right去链接cur的孩子
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							cout << "quit" << endl;
							return 0;
						}
					}
					delete cur;
				}
				
				else if (cur->_right == nullptr)//只有左孩子
				{
					if (cur == _root)//如果碰到删最后几个节点的情况
					{
						_root = cur->_left;//更新新的根
						//如果只有最后一个节点,_root变成nullptr,然后cur被delete
					}
					else
					{
						//判断一下parent用left还是right去链接cur的孩子
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							cout << "quit" << endl;
							return 0;
						}
					}
					delete cur;
				}

				else//左右都有孩子,替换法
				{
					//通过中序找右树中的最小节点
					Node* t = cur->_right;
					Node* parent = cur;//记录t的父节点
					while (t->_left)
					{
						parent = t;
						t = t->_left;
					}
					swap(cur->_key, t->_key);
					//交换后看t是parent的左还是右
					if (t == parent->_left)
					{
						//t已经是最左,所以只可能有右孩子
						parent->_left = t->_right;
					}
					else if (t == parent->_right)
					{
						parent->_right = t->_right;
					}
					else
					{
						cout << "quit" << endl;
						return 0;
					}
					delete t;
				}
				return true;
			}
		}
		return false;
	}
	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 InsertR(const K& key)
	{
		return _InsertR(_root,key);
	}
	bool EraseR(const K& key)
	{
		return _EraseR(_root,key);
	}
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	~BSTree()
	{
		Destroy(_root);
	}
protected:
	void Destroy(Node* &root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newnode = new Node(root->_key);
		newnode->_left = copy(root->_left);
		newnode->_right = copy(root->_right);
		return newnode;
	}
	bool _FindR(Node* root,const K& key)
	{
		if (root == nullptr)
			return false;

		if (key < root->_key)
			return _FindR(root->_left, key);
		else if (key > root->_key)
			return _FindR(root->_right, key);
		else
			return true;
	}
	bool _InsertR(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key < root->_key)
			return _InsertR(root->_left, key);
		else if (key > root->_key)
			return _InsertR(root->_right, key);
		else
			return false;
	}
	bool _EraseR(Node*& root,const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (key < root->_key)
		{
			return _EraseR(root->_left, key);
		}
		else if (key > root->_key)
		{
			return _EraseR(root->_right, key);
		}
		else
		{
			if (root->_left == nullptr)//只有右孩子
			{
				Node* t = root;
				root = root->_right;
				delete t;
				return true;
			}
			else if (root->_right == nullptr)//只有左孩子
			{
				Node* t = root;
				root = root->_left;
				delete t;
				return true;
			}
			else
			{
				//和右树的最小节点替换,也就是右树的最左
				Node* t = root->_right;
				while (t->_left)
				{
					t = t->_left;
				}
				swap(root->_key, t->_key);
				//交换之后从头找是找不到的,但可以在右树找,然后再删除
				return _EraseR(root->_right, key);
			}
		}
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

int main()
{
	BSTree<int> at;
	int a[] = { 2,6,3,1,9,5,7,8,4 };
	for (auto e : a)
	{
		//cout << e << endl;
		at.InsertR(e);
	}
	at.InOrder();
	BSTree<int> bt;
	bt = at;
	bt.InOrder();
	cout << bt.FindR(5) << endl;
	cout << bt.FindR(22) << endl;
	for (auto e : a)
	{
		//cout << e << endl;
		bt.EraseR(e);
		bt.InOrder();
	}

	bt.InOrder();
	return 0;
}

二叉搜索树的应用

K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。
比如:给一个单词word,判断该单词是否拼写正确,具体方式下:

  • 以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。

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

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

kv模型只需要在k模型的基础上做些许改动:

namespace kv
{
	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:
		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)
			{
				parent = cur;

				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					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
				{
					// 准备删除  20:15继续
					if (cur->_left == nullptr)
					{//左为空
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
					}
					else if (cur->_right == nullptr)
					{//右为空
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
					}
					else
					{//左右都不为空

						// 右树的最小节点(最左节点)
						Node* parent = cur;
						Node* subLeft = cur->_right;
						while (subLeft->_left)
						{
							parent = subLeft;
							subLeft = subLeft->_left;
						}

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

						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
					}

					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 << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

}

统计次数:

int main()
{
	string arr[] = { "苹果", "苹果","香蕉", "菠萝", "西瓜", "椰子", "西瓜", "香蕉", "西瓜", "苹果", "菠萝"};
	kv::BSTree<string, int> countTree;
	for (auto& e : arr)
	{
		kv::BSTreeNode<string, int>* ret = countTree.Find(e);
		if (ret == nullptr)
		{
			countTree.Insert(e, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();

	return 0;
}

网站文章

  • 在Windows操作系统中安装MySQL8教程

    在Windows操作系统中安装MySQL8教程

    在Windows操作系统中安装MySQL8教程 1.1 下载MySQL8数据库 打开网址: https://www.mysql.com 点击DOWNLOADS菜单,显示界面如图1-xx所示。 点击“MySQL Community (GPL) Downloads »”链接,显示界面如图1-xx所示。 点击“MySQL Community Server”链接,显示界面如图1-xx所示。 点击...

    2024-04-01 00:01:17
  • 【SpringCloud-学习笔记】初识Docker

    【SpringCloud-学习笔记】初识Docker

    可以将程序及其依赖、运行环境一起打包为一个镜像,可以迁移到任意Linux操作系统运行时利用沙箱机制形成隔离容器,各个应用互不干扰启动、移除都可以通过一行命令完成,方便快捷docker是一个系统进程;虚...

    2024-04-01 00:01:09
  • ros 机械臂学习之ros control 学习笔记 2

    joint_trajectory_controller 接着上篇笔记聊该控制器。 - 轨迹表示 控制器采用模板化的方式,可以支持多种轨迹表达方式。 默认情况下采用了样条曲线插值法。 插值法的大致分为以...

    2024-04-01 00:00:43
  • 如何保证高可用?docker架构拓扑图

    如何保证高可用?docker架构拓扑图

    架构筑基大家都知道,性能一直是让程序员比较头疼的问题。当系统架构变得复杂而庞大之后,性能方面就会下降,如果想成为一名优秀的架构师,性能优化就是你必须思考的问题。所以性能优化专题从JVM底层原理到内存优...

    2024-04-01 00:00:36
  • FindNextFile函数

    一、问题描述 使用FindFirstFile与FindNextFile遍历指定文件夹时,获取不到该文件夹下的文件。 class CMySharedFile; bool GetAllFiles(LPCTSTR lpDir, std::set&lt;CMySharedFile&gt; files); ...... std::set&lt;CMySharedF...

    2024-04-01 00:00:28
  • wordpress删除数据库中修订版本的文章数据

    wordpress删除数据库中修订版本的文章数据

    转载自 bcoder编程网 http://www.bcoder.cn/wordpress%e5%88%a0%e9%99%a4%e6%95%b0%e6%8d%ae%e5%ba%93%e4%b8%ad%e4%bf%ae%e8%ae%a2%e7%89%88%e6%9c%ac%e7%9a%84%e6%96%87%e7%ab%a0%e6%95%b0%e6%8d%ae/ 我们现在要做的就是删除wo

    2024-04-01 00:00:02
  • shell--正则表达式之awk

    一.awk工具的概述 在linux系统中,awk是一个功能强大的编辑工具,逐行读取输入文本,并根据指定的匹配模式进行查找,对符合条件的内容进行格式化输出或者过滤处理,可以在无交互的情况下实现相当复杂的文本操作,被广泛应用于shell脚本,完成各种自动化配置任务 二.awk的常见用法 awk的命令格式如下 awk 选项 ‘模式或条件 {编辑指令}’ 文件1 文件2... /...

    2024-03-31 23:59:55
  • -webkit-background-clip属性不生效问题

    -webkit-background-clip属性不生效问题

    将-webkit-text-fill-color改成color并且调整顺序。-webkit-background-clip属性不生效问题。试了好久,终于找到原因了,泪目( Ĭ ^ Ĭ )在浏览器勾选样式后又能够显示,排除浏览器不兼容。

    2024-03-31 23:59:51
  • kafka中的AR、ISR、LEO、HW分别是什么

    kafka中的AR、ISR、LEO、HW分别是什么

    AR: Assigned Replicas的缩写,是每个partition下所有副本(replicas)的统称; ISR: In-Sync Replicas的缩写,是指副本同步队列,ISR是AR中的一...

    2024-03-31 23:59:36
  • 从GPT到chatGPT(一):GPT1

    从GPT到chatGPT(一):GPT1

    GPT1,出自于OpenAI的论文,是最早的将transformer以多层堆叠的方式构成语言模型的模型,其出现时间早于BERT,但二者有一个最大的区别在于BERT只用的是transformer的enc...

    2024-03-31 23:59:11