基于面向对象的，C++实现二叉搜索树的一系列操作

1.树

树是由节点和边组成的一种可以表示数据的层次结构

根节点：树的最顶端的节点
叶节点：树的最底层的节点
子节点：通过边相连的位于下层的为子节点
父节点：通过边相连的位于上层的为父节点
层次：一个节点到根节点的距离称为层次
度：一个节点拥有子树的数量，如果一个树中所有节点的度都不大于n，那么这个树就是n叉树

2.二叉树

树中的每个节点最多只有两个节点称为二叉树

性质1：二叉树的每一层最多有2^i个节点
性质2：高度为k的二叉树的最大节点数为2^(k+1)-1，
性质3：二叉树的度为0的节点数m和度为2的节点数n满足：m=n+1

二叉树一般有三种：完美二叉树，完全二叉树，满二叉树

1.完美二叉树：二叉树的每一层都是满的，即深度为k的其节点数为2^(k+1)-1
2.完全二叉树：二叉树的节点从左到右没有空隙
3.满二叉树：每个非叶子节点的度均为2

在这里插入图片描述

3.二叉搜索树（BST）

左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值，所有而插不上中的值唯一，且可以通过深度优先搜索算法中的中序遍历方法即可按照值的升序来遍历二叉搜索树

3.1 BST的相关代码

3.1.1 TreeNode.h

#pragma once
class TreeNode
{
public:
	int value;
	TreeNode* left;
	TreeNode* right;

	TreeNode(int val);
	~TreeNode();
};

3.1.2 TreeNode.cpp

#include "TreeNode.h"

TreeNode::TreeNode(int val)
{
	this->value = val;
	left = nullptr;
	right = nullptr;
}

TreeNode::~TreeNode()
{
}

3.1.3 BST的相关代码

#pragma once
#include"TreeNode.h"


class BinarySearchTree
{
public:
	TreeNode* root;
	BinarySearchTree();
	~BinarySearchTree();

	bool insert(int val);//插入
	bool search(int val);//查找
	bool remove(int val);//删除
	void BFS();//Breadth First Search
	//Depth First Search:PreOrder,PostOrder,InOrder
	//PreOrder: 中左右
	void DFS_PreOrder(TreeNode* temp);
	void DFS_PreOrder();
	//InOrder：左中右
	void DFS_InOrder(TreeNode* temp);
	void DFS_InOrder();
	//PostOrder:左右中
	void DFS_PostOrder(TreeNode* temp);
	void DFS_PostOrder();
};

3.1.4 BST的相关代码

#include "BinarySearchTree.h"
#include <queue>
#include <iostream>

BinarySearchTree::BinarySearchTree()
{
	root = nullptr;
}

BinarySearchTree::~BinarySearchTree()
{
}

bool BinarySearchTree::insert(int val)
{
	TreeNode* newNode = new TreeNode(val);
	if (root == nullptr) {
		root = newNode;
		return true;
	}
	TreeNode* temp = root;
	while (true) {
		if (newNode->value == temp->value) {
			return false;
		}
		if (newNode->value < temp->value) {
			if (temp->left == nullptr) {
				temp->left = newNode;
				return true;
			}
			temp = temp->left;
		}
		else {
			if (temp->right == nullptr) {
				temp->right = newNode;
				return true;
			}
			temp = temp->right;
		}
	}
}

bool BinarySearchTree::search(int val)
{
	if (root == nullptr) {
		return false;
	}
	TreeNode* temp = root;
	while (temp) {
		if (val < temp->value) {
			temp = temp->left;
		}
		else if (val > temp->value) {
			temp = temp->right;
		}
		else {
			return true;
		}
	}
	return false;
}

bool BinarySearchTree::remove(int val)
{
	TreeNode* temp = root;
	TreeNode* parent = nullptr;
	while (temp) {
		if (val < temp->value) {
			parent = temp;
			temp = temp->left;
		}
		else if(val > temp->value){
			parent = temp;
			temp = temp->right;
		}
		else {
			if (temp->left == nullptr) {//左孩子为空
				if (temp == root) {
					root = temp->right;
				}
				else if (temp == parent->left) {
					parent->left = temp->right;
				}
				else {
					parent->right = temp->right;
				}
			}
			else if (temp->right == nullptr) {//右孩子为空
				if (temp == root) {
					root = temp->left;
				}
				else if (temp = temp->left) {
					parent->left = temp->left;
				}
				else {
					parent->right = temp->left;
				}
			}
			else {//左右孩子都不为空：找左子树中的最大值或者右子树中的最小值
				TreeNode* maxleft = temp->left;
				parent = temp;
				while (maxleft->right) {//找左子树中的最大值
					parent = maxleft;
					maxleft = maxleft->right;
				}
				temp->value = maxleft->value;//交换
				if (parent->left == maxleft) {//此时删除的节点没有子节
					parent->left = maxleft->left;
				}
				else {//此时删除的节点只有一个子节点
					parent->right = maxleft->left;
				}
			}
			return true;
		}
	}
	return false;
}

void BinarySearchTree::BFS()
{
	std::queue<TreeNode*> myQueue;
	myQueue.push(root);
	while (myQueue.size() > 0) {
		TreeNode* temp = myQueue.front();
		myQueue.pop();
		std::cout << temp->value << " ";

		if (temp->left != nullptr) {
			myQueue.push(temp->left);
		}
		if (temp->right != nullptr) {
			myQueue.push(temp->right);
		}
	}
}

void BinarySearchTree::DFS_PreOrder(TreeNode* temp)
{
	std::cout << temp->value << " ";
	if (temp->left != nullptr) {
		DFS_PreOrder(temp->left);
	}
	if (temp->right != nullptr) {
		DFS_PreOrder(temp->right);
	}
}

void BinarySearchTree::DFS_PreOrder()
{
	DFS_PreOrder(root);
}

void BinarySearchTree::DFS_InOrder(TreeNode* temp)
{
	if (temp->left != nullptr) {
		DFS_InOrder(temp->left);
	}
	std::cout << temp->value << " ";
	if (temp->right != nullptr) {
		DFS_InOrder(temp->right);
	}
}

void BinarySearchTree::DFS_InOrder()
{
	DFS_InOrder(root);
}

void BinarySearchTree::DFS_PostOrder(TreeNode* temp)
{
	if (temp->left != nullptr) {
		DFS_PostOrder(temp->left);
	}
	if (temp->right != nullptr) {
		DFS_PostOrder(temp->right);
	}
	std::cout << temp->value << " ";
}

void BinarySearchTree::DFS_PostOrder()
{
	DFS_PostOrder(root);
}

3.2 BST的先序

先序遍历：根节点->左子树->右子树

在这里插入图片描述

void BinarySearchTree::DFS_PreOrder(TreeNode* temp)
{
	std::cout << temp->value << " ";
	if (temp->left != nullptr) {
		DFS_PreOrder(temp->left);
	}
	if (temp->right != nullptr) {
		DFS_PreOrder(temp->right);
	}
}

void BinarySearchTree::DFS_PreOrder()
{
	DFS_PreOrder(root);
}

3.3 BST的中序

中序遍历：左子树->根节点->右子树

在这里插入图片描述

//中序：左中右
void BinarySearchTree::DFS_InOrder(TreeNode* temp)
{
	if (temp->left != nullptr) {
		DFS_InOrder(temp->left);
	}
	std::cout << temp->value << " ";
	if (temp->right != nullptr) {
		DFS_InOrder(temp->right);
	}
}

void BinarySearchTree::DFS_InOrder()
{
	DFS_InOrder(root);
}

3.4 BST的后序

后序遍历：左子树->右子树->根节点

在这里插入图片描述

void BinarySearchTree::DFS_PostOrder(TreeNode* temp)
{
	if (temp->left != nullptr) {
		DFS_PostOrder(temp->left);
	}
	if (temp->right != nullptr) {
		DFS_PostOrder(temp->right);
	}
	std::cout << temp->value << " ";
}

void BinarySearchTree::DFS_PostOrder()
{
	DFS_PostOrder(root);
}

3.5 BST的层序遍历

层序遍历：从上到下，从左到右

在这里插入图片描述

void BinarySearchTree::BFS()
{
	std::queue<TreeNode*> myQueue;
	myQueue.push(root);
	while (myQueue.size() > 0) {
		TreeNode* temp = myQueue.front();
		myQueue.pop();
		std::cout << temp->value << " ";

		if (temp->left != nullptr) {
			myQueue.push(temp->left);
		}
		if (temp->right != nullptr) {
			myQueue.push(temp->right);
		}
	}
}

3.5 BST的插入

1.创造新节点
2.判断新节点与root节点的大小
3.在判断root相应的子节点是否为空：
为空就直接插入，不为空就反复循环上述2,3步骤

在这里插入图片描述

bool BinarySearchTree::insert(int val)
{
	TreeNode* newNode = new TreeNode(val);
	if (root == nullptr) {
		root = newNode;
		return true;
	}
	TreeNode* temp = root;
	while (true) {
		if (newNode->value == temp->value) {
			return false;
		}
		if (newNode->value < temp->value) {
			if (temp->left == nullptr) {
				temp->left = newNode;
				return true;
			}
			temp = temp->left;
		}
		else {
			if (temp->right == nullptr) {
				temp->right = newNode;
				return true;
			}
			temp = temp->right;
		}
	}
}

3.6 BST的删除

1.删除的节点没有子节点：
（1）如果删除节点是左子节点，将其父节点的指针设为nullptr
（2）如果删除节点是右子节点，将其父节点的指针设为nullptr
2.删除的节点有一个子节点：
（1）如果删除节点是左子节点，将其父节点的左指针指向删除节点的子节点
（2）如果删除节点是右子节点，将其父节点的右指针指向删除节点的子节点
3.删除的节点有两个子节点：
（1）从删除节点的左子树中查找value最大的节点（或者右子树中的最小值）
（2）将找到的节点移动到删除位置
（3）交换待删除的节点和左子树的最大值（或者右子树中的最小值）
（4）删除已经移动的节点

在这里插入图片描述
在这里插入图片描述

bool BinarySearchTree::remove(int val)
{
	TreeNode* temp = root;
	TreeNode* parent = nullptr;
	while (temp) {
		if (val < temp->value) {
			parent = temp;
			temp = temp->left;
		}
		else if(val > temp->value){
			parent = temp;
			temp = temp->right;
		}
		else {
			if (temp->left == nullptr) {//左孩子为空
				if (temp == root) {
					root = temp->right;
				}
				else if (temp == parent->left) {
					parent->left = temp->right;
				}
				else {
					parent->right = temp->right;
				}
			}
			else if (temp->right == nullptr) {//右孩子为空
				if (temp == root) {
					root = temp->left;
				}
				else if (temp = temp->left) {
					parent->left = temp->left;
				}
				else {
					parent->right = temp->left;
				}
			}
			else {//左右孩子都不为空：找左子树中的最大值或者右子树中的最小值
				TreeNode* maxleft = temp->left;
				parent = temp;
				while (maxleft->right) {//找左子树中的最大值
					parent = maxleft;
					maxleft = maxleft->right;
				}
				temp->value = maxleft->value;//交换
				if (parent->left == maxleft) {//此时删除的节点没有子节
					parent->left = maxleft->left;
				}
				else {//此时删除的节点只有一个子节点
					parent->right = maxleft->left;
				}
			}
			return true;
		}
	}
	return false;
}

3.7 BST的查找

根据二叉搜索树的定义进行查找：比节点大的往右边走，比节点小的往左边走

在这里插入图片描述

bool BinarySearchTree::search(int val)
{
	if (root == nullptr) {
		return false;
	}
	TreeNode* temp = root;
	while (temp) {
		if (val < temp->value) {
			temp = temp->left;
		}
		else if (val > temp->value) {
			temp = temp->right;
		}
		else {
			return true;
		}
	}
	return false;
}

4.测试

#include<iostream>
#include"BinarySearchTree.h"
using namespace std;

void test03() {
	BinarySearchTree* mybst3 = new BinarySearchTree();
	mybst3->insert(4);
	mybst3->insert(2);
	mybst3->insert(6);
	mybst3->insert(1);
	mybst3->insert(3);
	mybst3->insert(5);
	mybst3->insert(7);

	cout << "先序：";
	mybst3->DFS_PreOrder();
	cout << endl;
	cout << "中序：";
	mybst3->DFS_InOrder();
	cout << endl;
	cout << "后序：";
	mybst3->DFS_PostOrder();
	cout << endl;
	cout << "层序：";
	mybst3->BFS();
}

void test05() {
	BinarySearchTree* mybst5 = new BinarySearchTree();
	mybst5->insert(4);
	mybst5->insert(2);
	mybst5->insert(6);
	mybst5->insert(1);
	mybst5->insert(3);
	mybst5->insert(5);
	mybst5->insert(7);

	cout << "删除前：";
	mybst5->DFS_InOrder();
	cout << endl;
	mybst5->remove(6);
	cout << "删除后：";
	mybst5->DFS_InOrder();
}
int main() {
	test03();
	cout << endl;
	cout << "---------------------------------" << endl;
	test05();
}

在这里插入图片描述

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

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

相关文章

HashMap学习和线程安全的HashMap

HashMap学习和线程安全的HashMap

HashMap的底层数据结构&#xff1f; HashMap在JDK1.8里面的Node数组加链表加红黑树&#xff0c;当链表长度大于8且数组长度大于64&#xff0c;链表转化为红黑树。当红黑树节点数小于6&#xff0c;红黑树转化为链表。在JDK1.7中是数组加链表。 为什么要用红黑树&#xff1f; 当…
阅读更多...
【C语言】- 设置控制台文字颜色、大小和字体

【C语言】- 设置控制台文字颜色、大小和字体

【C语言】- 设置控制台标题、编码、文字颜色、大小和字体 文章目录 【C语言】- 设置控制台标题、编码、文字颜色、大小和字体1 - 设置控制台标题2 - 设置控制台编码3 - 设置控制台字体和大小参考链接 1 - 设置控制台标题 因为要用到 Windows API&#xff0c;所以需要包含头文件…
阅读更多...
hub汉语有轮毂的意思吗？

hub汉语有轮毂的意思吗？

问题描述&#xff1a;hub汉语有轮毂的意思吗&#xff1f; 问题解答&#xff1a; 是的&#xff0c;"hub"&#xff08;中文翻译为"轮毂"&#xff09;是指机械装置中的一个中心部分&#xff0c;通常用于连接或支持其他部分。在车辆的轮胎系统中&#xff0c;…
阅读更多...
算法学习系列（二十四）：二分图

算法学习系列（二十四）：二分图

目录 引言一、二分图二、染色法三、匈牙利算法 引言 这个二分图作为平常我是不怎么知道的&#xff0c;但是在算法竞赛中还是能用得到的。本文主要介绍了染色法&#xff1a;用来判断如否为二分图&#xff0c;匈牙利算法&#xff1a;求出二分图最大匹配数。 一、二分图 二分图…
阅读更多...
【Linux】权限的深度解析

【Linux】权限的深度解析

前言&#xff1a;在此之前我们学习了一些常用的Linux指令&#xff0c;今天我们进一步学习Linux下权限的一些概念 &#x1f496; 博主CSDN主页:卫卫卫的个人主页 &#x1f49e; &#x1f449; 专栏分类:Linux的学习 &#x1f448; &#x1f4af;代码仓库:卫卫周大胖的学习日记&a…
阅读更多...
全流程机器视觉工程开发（一）环境准备，paddledetection和labelme

全流程机器视觉工程开发（一）环境准备，paddledetection和labelme

前言 我现在在准备做一个全流程的机器视觉的工程&#xff0c;之前做了很多理论相关的工作。大概理解了机器视觉的原理&#xff0c;然后大概了解了一下&#xff0c;我发现现在的库其实已经很发展了&#xff0c;完全不需要用到非常多的理论&#xff0c;只需要知道开发过程就可以…
阅读更多...
HFSS笔记/信号完整性分析（一）——常用快捷键+建模技巧

HFSS笔记/信号完整性分析（一）——常用快捷键+建模技巧

文章目录 1、常用快捷键2、常用建模技巧2.1 如何由一个无厚度的sheet生成一个有厚度的2.2 如何绘制T形截面的传输线&#xff1f;2.3 自动建立辐射边界法一、法二、 仅做笔记整理与分享。 1、常用快捷键 快捷键功能CtrlDfit it all 以合适的尺寸至于窗口中间CtrlH隐藏object或者…
阅读更多...
【XTuner 大模型单卡低成本微调实战】学习笔记

【XTuner 大模型单卡低成本微调实战】学习笔记

参考学习教程【XTuner 大模型单卡低成本微调实战】 理论 Finetune简介 大语言模型 微调模式 增量预训练 指令跟随微调 LoRA和QLoRA Xtuner介绍 实战 自定义微调 用 Medication QA 数据集进行微调 将数据转为 XTuner 的数据格式 目标格式&#xff1a;(.jsonL) 写提示词请C…
阅读更多...
算法练习-A+B/财务管理/实现四舍五入/牛牛的菱形字符（题目链接+题解打卡）

算法练习-A+B/财务管理/实现四舍五入/牛牛的菱形字符（题目链接+题解打卡）

难度参考 难度&#xff1a;简单 分类&#xff1a;熟悉OJ与IDE的操作 难度与分类由我所参与的培训课程提供&#xff0c;但需要注意的是&#xff0c;难度与分类仅供参考。以下内容均为个人笔记&#xff0c;旨在督促自己认真学习。 题目 A B1. A B - AcWing题库财务管理1004:财…
阅读更多...
C语言学习之字典（单词拆分）

C语言学习之字典（单词拆分）

实例要求&#xff1a; 1、给定字符串以及字符串列表作为字典&#xff1b; 2、判断是否可以利用字典中出现的单词拼接出字符串&#xff1b; 3、不要求字典中出现的单词全部都使用&#xff1b; 4、字典中的单词可以重复使用&#xff1b; 实例分析&#xff1a; 1、初始化数组…
阅读更多...
对java的interface的理解

对java的interface的理解

一个例子来让我们理解更加深刻 这是我们的整体文件布局 ①A是接口 ②B和C是用来实现接口的类 ③show是我们的运行函数&#xff0c;用来展示 A接口 接口中定义的方法可以不用去实现,用其他类去实现(必须实现) 关键字:interface public interface A { // public static …
阅读更多...
Android Activity的启动流程（Android-10）

Android Activity的启动流程（Android-10）

前言 在Android开发中&#xff0c;我们经常会用到startActivity(Intent)方法&#xff0c;但是你知道startActivity(Intent)后Activity的启动流程吗&#xff1f;今天就专门讲一下最基础的startActivity(Intent)看一下Activity的启动流程&#xff0c;同时由于Launcher的启动后续…
阅读更多...
JavaEE学习笔记 2024-1-12 --Tomcat服务器、Servlet

JavaEE学习笔记 2024-1-12 --Tomcat服务器、Servlet

JavaEE 个人整理非商业用途&#xff0c;欢迎探讨与指正&#xff01;&#xff01; JavaEE是企业级开发 是综合性非常强的阶段  包含的知识点:JavaSE,MySQL,JDBC,WEB(HTML,CSS,JS,前端框架),Servlet,JSP,XML,AJAX等技术 目录 JavaEE1.服务器2.Tomcat服务器2.1Tomcat的使用2.2Tom…
阅读更多...
【驱动】I2C驱动分析(二)-驱动框架

【驱动】I2C驱动分析(二)-驱动框架

I2C驱动框架简介 I2C 驱动属于总线-设备-驱动模型的&#xff0c;与I2C总线设备驱动模型相比&#xff0c;大体框架是一样&#xff0c;系统的整体框架如下所示。 最上层是应用层&#xff0c;在应用层用户可以直接用open read write对设备进行操作&#xff0c;往下是设备驱动层&a…
阅读更多...
SpringBoot 中使用 Quartz 创建定时任务

SpringBoot 中使用 Quartz 创建定时任务

文章目录 一、使用示例二、运行原理 一、使用示例 自定义 job&#xff1a; Slf4j public class MyJob extends QuartzJobBean {Overrideprotected void executeInternal(JobExecutionContext context) throws JobExecutionException {log.info("MyJob start...");l…
阅读更多...
【unity】麦克风声音驱动，控制身体做出不同动作

【unity】麦克风声音驱动，控制身体做出不同动作

1.在角色对象上挂在animator组件&#xff0c;并将动作控制器与其关联 2.在角色对象上挂在audio source组件。 3.新建voice control脚本&#xff0c;编写代码如下&#xff1a; using System; using System.Collections; using System.Collections.Generic; using UnityEngine;…
阅读更多...
【OJ】牛客链表刷题

【OJ】牛客链表刷题

题目 1. 链表分割1.1 题目分析1.2 代码 2. 链表的回文结构2.1 题目分析2.2 代码 这里两道与链表有关的题目均来自牛客。 1. 链表分割 1.1 题目分析 因为这里代码不能选择用c语言写&#xff0c;所以选择用c,因为c兼容c。 题目要求分割链表&#xff0c;我们可以直接弄成两个带哨…
阅读更多...
Codeforces Round 915 (Div. 2) D题 单调栈，特殊情况入手

Codeforces Round 915 (Div. 2) D题 单调栈，特殊情况入手

Problem - D - Codeforces 目录 题意&#xff1a; 思路&#xff1a; 把0放后面&#xff1a; ———— 然后看懂下面思路&#xff0c;理解单调栈&#xff1a; 细节&#xff1a; 核心代码&#xff1a; 题意&#xff1a; mex指的是该数组缺的最小的自然数&#xff0c;例如…
阅读更多...
2024最有发展潜力的代理项目！格行随身wifi代理项目分析测评，轻资产靠谱创业项目推荐

2024最有发展潜力的代理项目！格行随身wifi代理项目分析测评，轻资产靠谱创业项目推荐

最近很多网友都有创业的想法&#xff0c;身边创业的朋友也不在少数&#xff0c;当然有成功的&#xff0c;也有亏的血本无归的。最近网上也有很多适合新手的创业或代理项目&#xff0c;什么单身经济啊&#xff0c;大健康啊还有创业圈一直在讨论的随身WiFi代理等。当然一些创投圈…
阅读更多...
大文件的断点续传如何实现

大文件的断点续传如何实现

断点续传 断点续传是一种数据恢复技术&#xff0c;主要用于在读取或发送数据时&#xff0c;因为网络问题、磁盘问题等原因导致数据传输中断。断点续传技术允许你在已经传输的数据基础上继续传输&#xff0c;从而节省数据传输时间。 断点续传通常用于文件传输过程中&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023