C++进阶 二叉搜索树的讲解

在这里插入图片描述

二叉搜索树的概念

二叉搜索树又称为二叉排序树。

  • 二叉搜索树的性质
    • 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
    • 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
    • 它的左右子树也分别为二叉搜索树
    • 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值。

二叉搜索树的插入

    1. 树为空，则直接新增结点，赋值给 root 指针
    1. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
    1. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

例子:

int a[] = {8, 3, 1, 10, 1 6, 4, 7, 14, 13};

请添加图片描述

代码:

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){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, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

二叉搜索树的查找

    1. 从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。
    1. 最多查找高度次，走到到空，还没找到，这个值不存在。
    1. 如果不支持插入相等的值，找到 x 即可返回。
    1. 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

代码:

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

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

  1. 要删除结点 N 左右孩子均为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点
  2. 要删除的结点 N 左孩子位空，右孩子结点不为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点
  3. 要删除的结点 N 右孩子位空，左孩子结点不为空
    • 解决方法：把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点
  4. 要删除的结点 N 左右孩子结点均不为空
    • 解决方法：无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。**找 N 左子树的值最大结点 R(最右结点)**或者 N 右子树的值最小结点 R(最左结点)替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

代码:

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{//找到了目标节点,进行删除操作if (cur->_left == nullptr)//左节点为空{if (cur == _root)//如果是根节点，就将根节点的右子节点设置为根节点{_root = cur->_right;}else{if (parent->_left == cur)//如果父节点的左节点是当前节点{parent->_left = cur->_right;//将父节点的左节点连接至当前节点的右子节点。}else//如果父节点的右节点是当前节点{parent->_right = cur->_right;//将父节点的右节点连接至当前节点的右子节点。}}delete cur;//删除当前节点}else if (cur->_right == nullptr)//右节点为空{if (cur == _root)//如果是根节点，就将根节点的左子节点设置为根节点{_root = cur->_left;}else{if (parent->_left == cur)//如果父节点的左节点是当前节点{parent->_left = cur->_left;//将父节点的左节点连接至当前节点的左子节点。}else//如果父节点的右节点是当前节点{parent->_right = cur->_left;//将父节点的右节点连接至当前节点的左子节点。}}delete cur;//删除当前节点}else{// 左右节点都不为空// 这里默认替换右子树最左节点cNode *replaceParent = cur;Node *replace = cur->_right;//进入根节点的右子树while (replace->_left)//迭代左节点，找到右子树的最左节点{replaceParent = replace;//记录父节点replace = replace->_left;//迭代左节点}//此时替换节点（replace）的左节点一定为空cur->_key = replace->_key;//交换值if (replaceParent->_left == replace)//如果替换节点是左节点replaceParent->_left = replace->_right;//将父节点的左赋值为替换节点的右，因为替换节点的左节点一定是空的，因为是按照根节点的右子树的最左节点查找的。else//如果替换节点是右节点replaceParent->_right = replace->_right;//将父节点的右赋值为替换节点的右，因为替换节点的左节点一定是空的，因为是按照根节点的右子树的最左节点查找的。delete replace;//删除替换节点}return true;}}return false;
}

二叉搜索树的析构

  • 递归析构
public:
~BSTree()
{Destroy(_root);_root = nullptr;
}private:
void Destroy(Node *root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

二叉搜索树的深拷贝

BSTree(const BSTree &t)
{_root = Copy(t._root);
}Node *Copy(Node *root)
{if (root == nullptr)return nullptr;Node *newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;
}

二叉搜索树的=重载

BSTree &operator=(BSTree tmp)
{swap(_root, tmp._root);//tmp为拷贝，可以直接交换，不影响tmpreturn *this;
}

完整代码

#pragma once
#include <iostream>
using namespace std;template <class K>
struct BSTNode
{K _key;BSTNode<K> *_left;BSTNode<K> *_right;BSTNode(const K &key): _key(key), _left(nullptr), _right(nullptr){}
};namespace key
{template <class K>class BSTree{typedef BSTNode<K> Node;public:bool Insert(const K &key) // 二叉树的插入{if (_root == nullptr){_root = new Node(key);return true;}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{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}void Inorder() // 中序遍历{_Inorder(_root);}bool 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 true;}}return false;}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{// 找到了要删除的节点// 删除// 左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) // 右为空{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node *replaceParent = cur;Node *replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;}private:void _Inorder(Node *root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ' ';_Inorder(root->_right);}private:Node *_root = nullptr;};}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

vscode搭建ros开发环境问题记录（更新...）

vscode搭建ros开发环境问题记录（更新...）

文章目录 vscode 不能自动补全 开发环境&#xff1a; vmware 15.7 ubuntu 20.04 ros noetic vscode 不能自动补全 这里将头文件已经正确包含到c_cpp_properties.json中代码中仍然不能自动补全&#xff0c; 将C_CPP插件设置中的Intelli Sense Engine 设置为TagParser,然后重新加…
阅读更多...
MySQL:基本查询操作

MySQL:基本查询操作

插入 基本插入语法&#xff1a; insert [into] 表名 (列1, 列2 ...) values (值1, 值2 ...); create table students( id int unsigned primary key auto_increment, sn int not null unique comment 学号, name varchar(20) not null, tel varchar(20) );一次性指定所有值&…
阅读更多...
损耗金属件检测系统源码分享

损耗金属件检测系统源码分享

损耗金属件检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer V…
阅读更多...
25达能笔试测评秋招校招认知和行为偏好测评题型分析

25达能笔试测评秋招校招认知和行为偏好测评题型分析

达能认知和行为偏好测评笔试测评用的游戏化测评数字推理&#xff0c;具体有四类&#xff1a; 职业行为测试&#xff1a;从选项中选择你更偏向的那个&#xff0c;在选择的时候就可以往达能的企业文化相关方向靠。 motion challenge&#xff1a;类似华容道呢&#xff0c;要用最…
阅读更多...
18063 圈中的游戏

18063 圈中的游戏

### 思路 1. 创建一个循环链表表示围成一圈的 n 个人。 2. 从第一个人开始报数&#xff0c;每报到 3 的人退出圈子。 3. 重复上述过程&#xff0c;直到只剩下一个人。 4. 输出最后留下的人的编号。 ### 伪代码 1. 创建一个循环链表&#xff0c;节点表示每个人的编号。 2. 初始…
阅读更多...
初识软件测试

初识软件测试

目录 一、什么是测试 1. 生活中的测试场景 2. 为什么需要软件测试 3. 软件测试定义 二、测试的岗位有哪些 1. 软件测试开发工程师 2. 测试工程师 &#x1f334;高频面试题&#xff1a; 三、软件测试和开发的区别 1. 工作内容 2. 难易程度上 3. 工作环境 4. Money …
阅读更多...
【WPF】桌面程序开发之xaml页面绑定数据模型详解

【WPF】桌面程序开发之xaml页面绑定数据模型详解

使用Visual Studio开发工具&#xff0c;我们可以编写在Windows系统上运行的桌面应用程序。其中&#xff0c;WPF&#xff08;Windows Presentation Foundation&#xff09;项目是一种常见的选择。然而&#xff0c;对于初学者来说&#xff0c;WPF项目中xaml页面的布局设计可能是一…
阅读更多...
java项目之在线考试与学习交流网页平台源码（springboot）

java项目之在线考试与学习交流网页平台源码（springboot）

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的在线考试与学习交流网页平台。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 基于JAVA语言…
阅读更多...
C++数据结构-树的概念及分类介绍（基础篇）

C++数据结构-树的概念及分类介绍（基础篇）

1.什么是树 树是数据结构中的一种&#xff0c;其属于非线性数据结构结构的一种&#xff0c;我们前文所提到的数据结构多数都是线性的&#xff0c;这也是较为简单的数据结构&#xff0c;而接下来的树与图均属于非线性数据结构&#xff0c;也是概念极多的一类。 树是由结点或顶…
阅读更多...
OSS对象资源管理

OSS对象资源管理

1、登录aliyun 1.1、什么是OSS&#xff1f;有什么用&#xff1f; OSS 是“Object Storage Service”的缩写&#xff0c;中文常称为“对象存储服务”。OSS 是一种互联网云存储服务&#xff0c;主要用于海量数据的存储与管理。 相较于nginx&#xff0c;OSS更灵活&#xff0c;不…
阅读更多...
yolov8 pose姿态关键点识别动物姿态识别

yolov8 pose姿态关键点识别动物姿态识别

导言 介绍了 Tiger数据集&#xff0c;这是一个专为姿势估计任务设计的多功能数据集。该数据集由来自YouTube 视频的 263 张图片组成&#xff0c;其中 210 张用于训练&#xff0c;53 张用于验证。它是测试姿势估计算法和排除故障的绝佳资源。 尽管虎姿态数据集只有 210 张图像…
阅读更多...
AT89C51 Intel HEX手工结构分析 反汇编工具

AT89C51 Intel HEX手工结构分析 反汇编工具

在不查询格式情况下分析确定 Intel HEX 格式 Hex文件内容 :0300000002090BE7 :0C090B00787FE4F6D8FD7581080208F63C :01091700419E :1008F60078087C007D007BFF7A0979177E007F01EE :050906001208D080FE84 :10080000E709F608DFFA8046E709F208DFFA803EDA :1008100088828C83E709F0…
阅读更多...
9.15 BFS中等 133 Clone Graph review 138 随机链表的复制

9.15 BFS中等 133 Clone Graph review 138 随机链表的复制

133 Clone Graph //错误代码class Solution { public:Node* cloneGraph(Node* node) {//邻接表、BFS---》类似于二叉树的层次遍历if(!node || !node->val) return node;//构造队列queue<Node*> prev;prev.push(node);//构造新的图结点列表vector<Node*> adjList…
阅读更多...
用Spring Boot搭建的读书笔记分享平台

用Spring Boot搭建的读书笔记分享平台

第1章 绪论 1.1课题背景 计算机的普及和互联网时代的到来使信息的发布和传播更加方便快捷。用户可以通过计算机上的浏览器访问多个应用系统&#xff0c;从中获取一些可以满足用户需求的管理系统。网站系统有时更像是一个大型“展示平台”&#xff0c;用户可以选择所需的信息进入…
阅读更多...
framework解决权限不足无法安装apk

framework解决权限不足无法安装apk

文件浏览器中安装apk权限不足 源码位置 base/services/core/java/com/android/server/uri/UriGrantsManagerService.java
阅读更多...
java数据结构----图

java数据结构----图

图的存储结构: 代码实现 public class Graph {// 标记顶点数目private int V;// 标记边数目private int E;// 邻接表private Queue<Integer>[] adj;public Graph(int v) {V v;this.E 0;this.adj new Queue[v];for (int i 0; i < adj.length; i) {adj[i] new Queu…
阅读更多...
初中（7-9年级）数学-人教版视频全套

初中（7-9年级）数学-人教版视频全套

文章目录 一、紧贴教材&#xff0c;内容全面二、生动讲解&#xff0c;易于理解三、灵活学习&#xff0c;随时随地四、获取方式 初中数学人教版视频全套&#xff0c;专为使用人教版教材的学生打造。通过高清视频、生动讲解和精准辅导&#xff0c;帮助学生轻松掌握数学知识点&…
阅读更多...
系统架构设计师教程 第5章 5.2 需求工程 笔记

系统架构设计师教程 第5章 5.2 需求工程 笔记

5.2 需求工程 ★★★★★ 软件需求是指用户对系统在功能、行为、性能、设计约束等方面的期望。 软件需求包括3个不同的层次&#xff1a;业务需求、用户需求和功能需求(也包括非功能需求)。 (1)业务需求 (business requirement) 反映了组织机构或客户对系统、产品高层次的目标…
阅读更多...
电信网络携手大模型：AI赋能网络运维的新范式

电信网络携手大模型：AI赋能网络运维的新范式

当电信网络用上大模型&#xff0c;会带来怎样的体验&#xff1f; 过去&#xff0c;网络出现问题时&#xff0c;运维人员需要依赖经验反复排查&#xff0c;找到“病根”后再“对症下药”。但在大模型的加持下&#xff0c;问题的解决方式发生了颠覆性的改变。 如今&#xff0c;…
阅读更多...
java项目之基于工程教育认证的计算机课程管理平台(源码+论文)

java项目之基于工程教育认证的计算机课程管理平台(源码+论文)

项目简介 基于工程教育认证的计算机课程管理平台的主要管理员可以管理教师&#xff0c;可以对教师信息修改删除以及查询操作&#xff1b;可以对通知公告信息进行添加&#xff0c;修改&#xff0c;删除以及查询操作&#xff1b;可以对学生信息进行添加&#xff0c;修改&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023