搜索二叉树（二叉搜索树）的实现（递归与非递归）

一、搜索二叉树的概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为搜索二叉树。 

二、搜索二叉树的操作

1. 搜索二叉树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

template <class K>
bool BSTree<K>::Find(const K& key)
{
	node* cur = _root;
	while (cur)
	{
		if (key < cur->_key)//小就往左走
		{
			cur = cur->_left;
		}
		else if (key > cur->_key)//大就往右走
		{
			cur = cur->_right;
		}
		else//找到了
		{
			return true;
		}
	}
	return false;
}

2. 搜索二叉树的插入

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按搜索二叉树性质查找插入位置，插入新节点

template <class K>
bool BSTree<K>::Insert(const K& key)
{
	//树为空，则直接新增节点，赋值给root指针
	if (_root == nullptr)
	{
		_root = new node(key);
		return true;
	}
	node* parent = nullptr;
	node* cur = _root;
	while (cur)//找到key该去的位置
	{
		parent = cur;
		if (cur->_key < key)//大就往右走
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)//小就往左走
		{
			cur = cur->_left;
		}
		else//有相等的值了无法再插入了
		{
			return false;
		}
	}
	if (parent->_key < key)
	{
		parent->_right = new node(key);
	}
	else
	{
		parent->_left = new node(key);
	}

	return true;
}

3.搜索二叉树的删除

删除的情况最为复杂，首先查找元素是否在搜索二叉树中，如果不存在，则返回, 否则要删除的结点分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

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

情况a：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况b：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况c：在它的右子树中寻找中序下的第一个结点(关键码最小)，或者在它的左子树中寻找中序下的第一个结点(关键码最大)用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除。

template <class K>
bool BSTree<K>::Erase(const K& key)
{
	node* parent = nullptr;
	node* cur = _root;
	while (cur)
	{
		
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//找到了就跳出循环
		{
			break;
		}
	}
	if (cur == nullptr)//cur走到空就意味着没找到
	{
		return false;
	}
	if (cur->_left == nullptr)//左为空 
	{
		if (cur == _root)
		{
			_root = cur->_right;
		}
		else if (cur == parent->_left)
		{
			parent->_left = cur->_right;
		}
		else if (cur == parent->_right)
		{
			parent->_right = cur->_right;
		}
		delete cur;
		return true;
	}
	else if (cur->_right == nullptr)//右为空
	{
		if (cur == _root)
		{
			_root = cur->_left;
		}
		else if (cur == parent->_left)
		{
			parent->_left = cur->_left;
		}
		else if (cur == parent->_right)
		{
			parent->_right = cur->_left;
		}
		delete cur;
		return true;
	}
	else//左右都不为空，去找它左树最大的节点替换它的值，再删除左树最大的节点
        //下面的图有做说明
	{
		node* parent = nullptr;
		node* leftMax = cur;
		while (leftMax->_right)//找到左树最大的节点
		{
			parent = leftMax;
			leftMax = leftMax->_right;
		}
		swap(cur->_key, leftMax->_key);//交换值
		if (parent->_left == leftMax)
		{
			parent->_left = leftMax->_left;
		}
		else
		{
			parent->_right = leftMax->_left;
		}
		delete leftMax;
		return true;
	}
	return false;
}

三、搜索二叉树的完整代码实现

#pragma once

#include <iostream>
using namespace std;


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

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

template <class K>
class BSTree
{
private:
	BSTreeNode<K>* _root;
	typedef BSTreeNode<K> node;
public:
	BSTree()
		:_root(nullptr)
	{

	}
	~BSTree()
	{
		Destroy(_root);
	}
	//增删查
	bool Insert(const K& key);
	bool Find(const K& key);
	bool Erase(const K& key);
	//中序遍历
	void InOrder();
	void _InOrder(node* root);
	//增删查的递归实现
	bool InsertR(const K& key);
	bool _InsertR(const K& key, node*& root);
	//为了对节点进行修改，这里的插入和删除的节点必须用引用传，这里是一个细节 
	bool EraseR(const K& key);
	bool _EraseR(const K& key, node*& root);
	bool FindR(const K& key);
	bool _FindR(const K& key, node* root);

	void Destroy(node* root);
};


template <class K>
bool BSTree<K>::Insert(const K& key)
{
	//树为空，则直接新增节点，赋值给root指针
	if (_root == nullptr)
	{
		_root = new node(key);
		return true;
	}
	node* parent = nullptr;
	node* cur = _root;
	while (cur)//找到key该去的位置
	{
		parent = cur;
		if (cur->_key < key)//大就往右走
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)//小就往左走
		{
			cur = cur->_left;
		}
		else//有相等的值了无法再插入了
		{
			return false;
		}
	}
	if (parent->_key < key)
	{
		parent->_right = new node(key);
	}
	else
	{
		parent->_left = new node(key);
	}

	return true;
}

template <class K>
bool BSTree<K>::Find(const K& key)
{
	node* cur = _root;
	while (cur)
	{
		if (key < cur->_key)//小就往左走
		{
			cur = cur->_left;
		}
		else if (key > cur->_key)//大就往右走
		{
			cur = cur->_right;
		}
		else//找到了
		{
			return true;
		}
	}
	return false;
}

template <class K>
bool BSTree<K>::Erase(const K& key)
{
	node* parent = nullptr;
	node* cur = _root;
	while (cur)
	{
		
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//找到了就跳出循环
		{
			break;
		}
	}
	if (cur == nullptr)//cur走到空就意味着没找到
	{
		return false;
	}
	if (cur->_left == nullptr)//左为空 
	{
		if (cur == _root)
		{
			_root = cur->_right;
		}
		else if (cur == parent->_left)
		{
			parent->_left = cur->_right;
		}
		else if (cur == parent->_right)
		{
			parent->_right = cur->_right;
		}
		delete cur;
		return true;
	}
	else if (cur->_right == nullptr)//右为空
	{
		if (cur == _root)
		{
			_root = cur->_left;
		}
		else if (cur == parent->_left)
		{
			parent->_left = cur->_left;
		}
		else if (cur == parent->_right)
		{
			parent->_right = cur->_left;
		}
		delete cur;
		return true;
	}
	else//左右都不为空，去找它左树最大的节点替换它的值，再删除左树最大的节点
	{
		node* parent = nullptr;
		node* leftMax = cur;
		while (leftMax->_right)//找到左树最大的节点
		{
			parent = leftMax;
			leftMax = leftMax->_right;
		}
		swap(cur->_key, leftMax->_key);//交换值
		if (parent->_left == leftMax)
		{
			parent->_left = leftMax->_left;
		}
		else
		{
			parent->_right = leftMax->_left;
		}
		delete leftMax;
		return true;
	}
	return false;
}

template <class K>
void BSTree<K>::_InOrder(node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);
}

template <class K>
void BSTree<K>::InOrder()
{
	_InOrder(_root);
	cout << endl;
}


template <class K>
bool BSTree<K>::EraseR(const K& key)
{
	return _EraseR(key, _root);
}


template <class K>
bool BSTree<K>::_EraseR(const K& key, node*& root)
{
	if (root == nullptr)
		return false;
	if (root->_key < key)
	{
		_EraseR(key, root->_right);
	}
	else if (root->_key > key)
	{
		_EraseR(key, root->_left);
	}
	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 _EraseR(key, root->_left);//交换完后去要删除节点的左子树删除最大的节点
		}
		delete del;
	}
	return true;
}

template <class K>
bool BSTree<K>::FindR(const K& key)
{
	return _FindR(key, _root);
}

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

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

template <class K>
void BSTree<K>::Destroy(node* root)
{
	if (root == nullptr)
		return;
	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}
//test.c

#include "BinarySearchTree.h"

int main()
{
	BSTree<int> bs;

	int arr[] = { 1,3,6,4,7,8,10,14,13 };
	for (auto e : arr)
	{
		bs.Insert(e);
	}
	bs.InOrder();

	bs.EraseR(1);
	bs.InOrder();

	bs.Insert(20);
	bs.InsertR(9);
	bs.InOrder();

	bool ret = bs.FindR(20);
	cout << ret << endl;


	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/161400.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

微信小程序动态生成表单来啦！你再也不需要手写表单了！

微信小程序动态生成表单来啦！你再也不需要手写表单了！

dc-vant-form 由于我们在小程序上涉及到数据采集业务&#xff0c;需要经常使用表单&#xff0c;微信小程序的表单使用起来非常麻烦&#xff0c;数据和表单是分离的&#xff0c;每个输入框都需要做数据处理才能实现响应式数据&#xff0c;所以我开发了dc-vant-form&#xff0c;…
阅读更多...
buildadmin+tp8表格操作（2）----表头上方按钮绑定事件处理，实现功能（全选/全不选）

buildadmin+tp8表格操作（2）----表头上方按钮绑定事件处理，实现功能（全选/全不选）

buildAdmin 表格上方的按钮添加完成之后&#xff0c; 就要对其实现功能了 有了上面的说明&#xff0c; 我就只要得到了 ref 中的表格对象&#xff0c; 就可以象el-table 一样来操作表格的属性和方法了 我们来实现上面的几个按钮的方法 全选/全不选 上面就是添加按钮功能的全过…
阅读更多...
小程序申请，商户号申请，微信支付开通操作流程

小程序申请，商户号申请，微信支付开通操作流程

总目录 文章目录 总目录前言1 申请商户号&#xff08;如已有商户号跳过&#xff09;1 申请流程与资料2 详细申请步骤 2 申请开通接入微信支付步骤3 申请微信小程序1 申请小程序步骤2 查看小程序AppID 4 微信支付普通商户与AppID账号关联结语 前言 本文主要讲解如何申请微信商户…
阅读更多...
私有云边界网络部署实践

私有云边界网络部署实践

业务背景 在私有云的业务场景中&#xff0c;常见的通信中包含了同VPC内虚机互访、不同VPC之间的虚机互访、VPC访问Underlay资源、VPC访问Internet资源、VPC提供服务&#xff0c;被Internet访问、VPC与专线网络之间互访等&#xff1b;实际应用中&#xff0c;大多数云业务通信场…
阅读更多...
vue解除数据双向绑定

vue解除数据双向绑定

let obj JSON.parse(JSON.stringify(data));例如&#xff0c;table列表中&#xff0c;点击编辑时&#xff0c;可对val进行如上操作来解除双向绑定
阅读更多...
运行软件报错mfc140.dll丢失？分享mfc140.dll丢失的解决方法

运行软件报错mfc140.dll丢失？分享mfc140.dll丢失的解决方法

小伙伴们&#xff0c;你是否也有过这样的经历&#xff1a;每当碰到诸如" mfc140.dll 丢失 "之类的烦人错误时&#xff0c;你是不是会一头雾水&#xff0c;完全不知道从何下手去解决&#xff1f;不要担心&#xff0c;接下来咱就给你提供这样一篇实用教程&#xff0c;教…
阅读更多...
适合家电和消费类应用R7F101GEE4CNP、R7F101GEG4CNP、R7F101GEG3CNP、R7F101GEE3CNP新一代RL78通用微控制器

适合家电和消费类应用R7F101GEE4CNP、R7F101GEG4CNP、R7F101GEG3CNP、R7F101GEE3CNP新一代RL78通用微控制器

典型应用 • 电机控制 • 电源 • 照明 • 一般用途 • 消费类应用 • 家用电器 • 工业自动化 • 楼宇自动化 器件选型 1、R7F101GEE4CNP&#xff1a;16BIT MCU RL78/G24 64K 40HWQFN -40C 至 125C 2、R7F101GEG4CNP&#xff1a;16BIT MCU RL78/G24 128K 40HWQFN -40C 至 …
阅读更多...
【linux】进行间通信——共享内存+消息队列+信号量

【linux】进行间通信——共享内存+消息队列+信号量

共享内存消息队列信号量 1.共享内存1.1共享内存的原理1.2共享内存的概念1.3接口的认识1.4实操comm.hppservice.cc &#xff08;写&#xff09;clint.cc &#xff08;读&#xff09; 1.5共享内存的总结1.6共享内存的内核结构 2.消息队列2.1原理2.2接口 3.信号量3.1信号量是什么3…
阅读更多...
IJ中配置TortoiseSVN插件：

IJ中配置TortoiseSVN插件：

文章目录 一、报错情况&#xff1a;二、配置TortoiseSVN插件&#xff1a; 一、报错情况&#xff1a; 由于公司电脑加密&#xff0c;TortoiseSVN菜单没有提交和更新按钮&#xff0c;所以需要使用IJ的SVN进行代码相关操作 二、配置TortoiseSVN插件&#xff1a; 需要设置一个svn.…
阅读更多...
肖sir__linux讲解vim命令（3.1）

肖sir__linux讲解vim命令（3.1）

vim 命令 一、 vi/vim 编辑器共分为三种模式&#xff1a; 格式 &#xff1a;vim 文件名 命令模式&#xff08;Command mode&#xff09;&#xff0c;“ESC”或ctrlc键 输入模式&#xff08;Insert mode&#xff09; 底线命令模式&#xff08;Last line mode&#xff09; …
阅读更多...
【uniapp】使用扫码插件，解决uni.scanCode扫码效率低的问题

【uniapp】使用扫码插件，解决uni.scanCode扫码效率低的问题

1. 背景 uniapp 中自带的二维码扫描的 API 是 uni.scanCode&#xff0c;但有如下问题&#xff1a; 二维码扫描的效率不高&#xff0c;有些需要扫2秒左右 较小或模糊的一些二维码无法识别出来&#xff0c;多次扫同样的一个码可能出现扫码失败的情况 受环境影响大&#xff0c…
阅读更多...
传输层——UDP协议

传输层——UDP协议

文章目录 一.传输层1.再谈端口号2.端口号范围划分3.认识知名端口号4.两个问题5.netstat与iostat6.pidof 二.UDP协议1.UDP协议格式2.UDP协议的特点3.面向数据报4.UDP的缓冲区5.UDP使用注意事项6.基于UDP的应用层协议 一.传输层 在学习HTTP等应用层协议时&#xff0c;为了便于理…
阅读更多...
从0开始学习JavaScript--JavaScript DOM操作与事件处理

从0开始学习JavaScript--JavaScript DOM操作与事件处理

在前端开发中&#xff0c;DOM&#xff08;文档对象模型&#xff09;是一个至关重要的概念&#xff0c;它为JavaScript提供了一种与HTML和XML文档交互的方法。本文将深入探讨DOM的概念与作用&#xff0c;以及JavaScript与DOM之间的密切关系。 DOM的概念与作用 DOM是什么&#…
阅读更多...
Vite 启动默认只能访问localhost解决方法

Vite 启动默认只能访问localhost解决方法

事情的经过是因为我需要测试本地项目的接口,然后因为burp默认不抓取localhost,127.0.0.1 .而且我也不想去修改burp. 所以我通过本地IP地址访问项目, 发现项目无法访问。 默认启动 所以特此记录一下。 在本地项目的package.json 中需要运行的脚本后 添加 --host即可。 具体如下…
阅读更多...
IIs部署发布vue项目测试环境

IIs部署发布vue项目测试环境

打开【控制面板 > 程序>启用或关闭Windows功能 】 1、安装IIS: 把这些勾选上&#xff0c;点击确定下载。 2、安装.net: 把这些勾选上&#xff0c;点击确定下载。 3、搜索IIs打开&#xff1a; 4、右击【网站>添加网站 】进行配置&#xff0c;点击确定。 4、右击[项目le…
阅读更多...
DRF纯净版项目搭建和配置

DRF纯净版项目搭建和配置

一、安装模块和项目 1.安装模块 pip install django pip install djangorestframework pip install django-redis # 按需安装 2.开启项目和api (venv) PS D:\pythonProject\env_api> django-admin startproject drf . (venv) PS D:\pythonProject\env_api> python ma…
阅读更多...
YOLOv8改进 | DAttention (DAT)注意力机制实现极限涨点

YOLOv8改进 | DAttention (DAT)注意力机制实现极限涨点

论文地址&#xff1a; DAT论文地址 官方地址&#xff1a;官方代码的地址 代码地址&#xff1a;文末有修改了官方代码BUG的代码块复制粘贴即可 一、本文介绍 本文给大家带来的是YOLOv8改进DAT(Vision Transformer with Deformable Attention)的教程&#xff0c;其发布于2022…
阅读更多...
使用 Python进行量化交易：前向验证分析

使用 Python进行量化交易：前向验证分析

运行环境&#xff1a;Google Colab 1. 利用 yfinance 下载数据 import yfinance as yfticker AAPL df yf.download(ticker) df下载苹果的股票数据 df df.loc[2018-01-01:].copy()dfdf[change_tomorrow] df[Adj Close].pct_change(-1) df.change_tomorrow df.change_tom…
阅读更多...
YOLOv8中训练参数中文解释

YOLOv8中训练参数中文解释

预测函数&#xff1a; from ultralytics import YOLO# Load a model model YOLO(yolov8n.pt) # Train the model model.train(datarD:\yolov8\ultralytics-main\data1.yaml, workers0, epochs100, batch16) 可选参数&#xff1a;
阅读更多...
el-table树形数据隐藏子选择框

el-table树形数据隐藏子选择框

0 效果 1 代码 type是table数据中用来区分一级和二级的标识 // 隐藏子合同选择框 cellNone(row) {if (row.row.type 3 || row.row.type 4) {return "checkNone";} }, <style lang"scss" scoped>::v-deep {.checkNone .el-checkbox__input {displa…
阅读更多...
最新文章

Copyright @ 2022~2023