C++——二叉树搜索树

前面写了初阶数据结构——二叉树；本文内容是来对它来进行结尾

目录

一概念

二实现

2.1查找

2.2插入 

2.3删除

完整源代码

三二叉树的应用 

 四二叉搜索树的性能分析

 五二叉搜索树相关的面试题

一概念

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

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

二实现

以下面的二叉搜索树为例：

2.1查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、走到到空，还没找到，这个值不存在。

bool find(const K& val)
{Node* cur = _root;while (cur){if (cur->_key < val){cur = cur->_right;}else if (cur->_key > val){cur = cur->_left;}else{//相等return true;}}return false;
}

2.2插入 

a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

bool insert(const K& val)
{if (_root == nullptr){_root = new Node(val);return true;}else{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < val){parent = cur;cur = cur->_right;}else if (cur->_key > val){parent = cur;cur = cur->_left;}else{//相等return false;}}//判断要在parent的左还是右进行插入cur = new Node(val);if (parent->_key > val){parent->_left = cur;}else{parent->_right = cur;}return true;}
}

2.3删除

a先通过二叉搜索树的性质找到节点的位置

b分析删除节点的左右孩子的情况：

无左右孩子节点(不考虑)

只有左孩子节点：删除之前把左孩子交给父亲节点

只有右孩子节点：删除之前把右孩子交给父亲节点

右孩子节点都有：有两种解决方法：

1找左节点的最大值的节点Max:Max的val与待删除的val进行交换；

2找右孩子的最小值的节点Min:Min的val与待删除的val进行交换；

以第二种为例来设计代码：

要注意对特殊情况的处理(删除根节点的情况)：

 

特别要记录cur(删除节点)的父节点(cur在父节点的左边还是右边不清楚) 

bool erase(const K& val)
{if (_root == nullptr) return false;Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < val){parent = cur;cur = cur->_right;}else if (cur->_key > val){parent = cur;cur = cur->_left;}else{//找到删除位置//右孩子为空if (cur->_right == nullptr){//cur是根节点if (parent == nullptr) _root = cur->_left;//cur的左孩子交给parentelse{if (parent->_left == cur) parent->_left = cur->_left;else if (parent->_right == cur) parent->_right = cur->_left;}delete cur;}//右孩子为空else if (cur->_left == nullptr){//cur==_rootif (parent == nullptr) _root = cur->_right;else{if (parent->_left == cur) parent->_left = cur->_right;else if (parent->_right == cur) parent->_right = cur->_right;}delete cur;}//都有else{//找到右节点的最小值进行替换删除（左节点的最大值）//要删除的可能是_root patent不能为nullptrNode* ParentRightMin = cur;Node* RightMin = cur->_right;while (RightMin->_left){ParentRightMin = RightMin;RightMin = RightMin->_left;}swap(RightMin->_key, cur->_key);//RightMin的右子树交给ParentRightMinif (ParentRightMin->_right == RightMin){ParentRightMin->_right = RightMin->_right;}else{ParentRightMin->_left = RightMin->_right;}delete RightMin;}return true;}}return false;
}

完整源代码


#pragma once
#include<iostream>
using namespace std;namespace bit
{template<class K>struct Node{Node(const K& key = K()):_left(nullptr), _right(nullptr), _key(key){}Node<K>* _left;Node<K>* _right;K _key;};template<class K>class BSTree{typedef Node<K> Node;public:bool insert(const K& val){if (_root == nullptr){_root = new Node(val);return true;}else{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < val){parent = cur;cur = cur->_right;}else if (cur->_key > val){parent = cur;cur = cur->_left;}else{//相等return false;}}//判断要在parent的左还是右进行插入cur = new Node(val);if (parent->_key > val){parent->_left = cur;}else{parent->_right = cur;}return true;}}bool find(const K& val){Node* cur = _root;while (cur){if (cur->_key < val){cur = cur->_right;}else if (cur->_key > val){cur = cur->_left;}else{//相等return true;}}return false;}bool erase(const K& val){if (_root == nullptr) return false;Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < val){parent = cur;cur = cur->_right;}else if (cur->_key > val){parent = cur;cur = cur->_left;}else{//找到删除位置//右孩子为空if (cur->_right == nullptr){//cur是根节点if (parent == nullptr) _root = cur->_left;//cur的左孩子交给parentelse{if (parent->_left == cur) parent->_left = cur->_left;else if (parent->_right == cur) parent->_right = cur->_left;}delete cur;}//右孩子为空else if (cur->_left == nullptr){//cur==_rootif (parent == nullptr) _root = cur->_right;else{if (parent->_left == cur) parent->_left = cur->_right;else if (parent->_right == cur) parent->_right = cur->_right;}delete cur;}//都有else{//找到右节点的最小值进行替换删除（左节点的最大值）//要删除的可能是_root patent不能为nullptrNode* ParentRightMin = cur;Node* RightMin = cur->_right;while (RightMin->_left){ParentRightMin = RightMin;RightMin = RightMin->_left;}swap(RightMin->_key, cur->_key);//RightMin的右子树交给ParentRightMinif (ParentRightMin->_right == RightMin){ParentRightMin->_right = RightMin->_right;}else{ParentRightMin->_left = RightMin->_right;}delete RightMin;}return true;}}return false;}//进行套壳void _InOrder(){InOrder(_root);cout << endl;}private:void InOrder(const Node* _root){if (_root == nullptr) return;InOrder(_root->_left);cout << _root->_key << " ";InOrder(_root->_right);}private:Node* _root=nullptr;};void Test1(){BSTree<int> sb;sb.insert(3);sb.insert(2);sb.insert(4);sb._InOrder();sb.erase(3);sb.erase(2);sb.erase(4);sb._InOrder();}
}

三二叉树的应用 

KV模型：

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对：

//对二叉搜索树进行改造：
template<class K,class V>
struct Node
{Node(const K& key = K(),const V& val=V()):_left(nullptr), _right(nullptr), _key(key),_val(val){}Node<K,V>* _left;Node<K,V>* _right;K _key;V _val;
};
template<class K,class V>
class BSTree
{typedef Node<K,V> Node;
public:bool Insert(const K& val,const K& valute){if (_root == nullptr){_root = new Node(val,valute);return true;}else{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < val){parent = cur;cur = cur->_right;}else if (cur->_key > val){parent = cur;cur = cur->_left;}else{//相等return false;}}//判断要在parent的左还是右进行插入if (parent->_key > val){parent->_left = new Node(val,valute);}else{parent->_right = new Node(val,valute);}return true;}}Node* Find(const V& val){Node* cur = _root;while (cur){if (cur->_key < val){cur = cur->_right;}else if (cur->_key > val){cur = cur->_left;}else{//相等return cur;}}return nullptr;}void _InOrder(){InOrder(_root);}private:void InOrder(const Node* _root){if (_root == nullptr) return;InOrder(_root->_left);cout << _root->_key << endl;InOrder(_root->_right);}Node* _root = nullptr;
};void Test1()
{// 输入单词，查找单词对应的中文翻译BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("left", "左边、剩余");dict.Insert("right", "右边");dict.Insert("sort", "排序");// 插入词库中所有单词string str;while (cin >> str){Node<string, string>* ret = dict.Find(str);if (ret == nullptr){cout << "单词拼写错误，词库中没有这个单词:" << endl;}else{cout << "中文翻译:" << ret->_val << endl;}}
}

 四二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 

但二叉搜索树在不同的场景可能会有以下结构：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：long2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N方

而在这种最差的情况下是有办法去去对它进行调整：将二叉树进行旋转，这个我们下文在说

 五二叉搜索树相关的面试题

 1. 二叉树创建字符串。oj链接
2. 二叉树的分层遍历1。oj链接
3. 二叉树的分层遍历2。oj链接
4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。oj链接
5. 二叉树搜索树转换成排序双向链表。oj链接
6. 根据一棵树的前序遍历与中序遍历构造二叉树。 oj链接
7. 根据一棵树的中序遍历与后序遍历构造二叉树。oj链接
8. 二叉树的前序遍历，非递归迭代实现 。oj链接
9. 二叉树中序遍历 ，非递归迭代实现。oj链接
10. 二叉树的后序遍历 ，非递归迭代实现。oj链接

以上便是我在学习二叉搜索树的相关内容，有错误欢迎在评论区指正，谢谢！！ 

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

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

相关文章

代码随想录——二叉树的右视图（Leetcode199）

代码随想录——二叉树的右视图（Leetcode199）

题目链接 层序遍历 思路&#xff1a;我们可以对二叉树进行层次遍历&#xff0c;那么对于每层来说&#xff0c;最右边的结点一定是最后被遍历到的。二叉树的层次遍历可以用广度优先搜索实现。 /*** Definition for a binary tree node.* public class TreeNode {* int val…
阅读更多...
蓝桥之链表

蓝桥之链表

最近真的特别焦虑&#xff0c;体测、比赛和考试一个接一个&#xff0c;让人喘不过气来QAQ 甚至考试和比赛还有冲突&#xff0c;sad 最近因为看了牙&#xff0c;打了药的缘故&#xff0c;一直在吃素QAQ 本来今天还想写个知识点总结的&#xff0c;但是太晚了&#xff0c;现在已…
阅读更多...
https免费证书获取

https免费证书获取

获取免费证书的网址&#xff1a; Certbot 1. 进入你的linux系统&#xff0c;先安装snapd&#xff0c; yum install snapd 2. 启动snapd service snapd start 3.安装 Certbot snap install --classic certbot 注意如下出现此错误时&#xff0c;需要先建立snap 软连接后&am…
阅读更多...
An 2024下载

An 2024下载

An2024下载&#xff1a; 百度网盘下载https://pan.baidu.com/s/1cQQCFL16OUY1G6uQWgDbSg?pwdSIMS Adobe Animate 2024&#xff0c;作为Flash技术的进化顶点&#xff0c;是Adobe匠心打造的动画与交互内容创作的旗舰软件。这款工具赋予设计师与开发者前所未有的创意自由&#x…
阅读更多...
CTF之love_math

CTF之love_math

这个题目简单看一下就知道要传参进行执行系统命令以达到找到flag的目的。 但是又可以发现过滤了很多东西。 这个题的绕过方法可以用到三个函数 base_convert(number,froombase,tobase)//分别为原始值&#xff0c;原来进制&#xff0c;要转换的进制dechex("十进制数"…
阅读更多...
mysql的存储结构

mysql的存储结构

一个表就是一个ibd文件 .ibd文件大小取决于数据和索引&#xff0c;在5.7之后才会为每个表生成一个独立表空间即一个ibd文件&#xff0c;在此之前&#xff0c;所有表默认下都会存储在“系统表空间”&#xff08;共享表空间&#xff09;&#xff0c;所有表都在一个ibd文件。 inn…
阅读更多...
与 Apollo 共创生态：Apollo 七周年大会带我体会自动驾驶技术的发展

与 Apollo 共创生态：Apollo 七周年大会带我体会自动驾驶技术的发展

前言 自动驾驶技术作为当今科技领域的热门话题&#xff0c;吸引着无数开发者和企业的目光。而在这个风起云涌的行业中&#xff0c;Apollo开放平台作为自动驾驶领域的领军者之一&#xff0c;扮演着不可或缺的角色。七年前&#xff0c;当Apollo开放平台刚刚起步时&#xff0c;也…
阅读更多...
Xshell 7官网免费版下载与安装详细教程！学校/家庭使用免费哦~

Xshell 7官网免费版下载与安装详细教程！学校/家庭使用免费哦~

一、 安装 1 卸载之前安装的xshell, 未安装忽略此步骤 2 解压本地文件&#xff0c;双击运行xshell**.exe, 按照提示安装 等候引导完成 3 点击下一步 4接受下一步 5 选择安装的路径 改成你自己的安装路径 6程序文件夹选择默认 7 取消勾选&#xff0c;激活之后操作 8 激活&…
阅读更多...
为什么推荐将 IoTDB 服务地址配置为 HostName 而非 IP？

为什么推荐将 IoTDB 服务地址配置为 HostName 而非 IP？

设置主机名启动 IoTDB 可在不修改配置情况下&#xff0c;在不同环境运行 IoTDB 并实现多次部署。 01 前言 IoTDB 在配置启动时有两种方式&#xff1a; 1. 通过设置 HostName&#xff08;主机名&#xff09;的方式来启动 IoTDB&#xff08;推荐方式&#xff09;&#xff1b; 2. …
阅读更多...
物联网设计竞赛_2_Ubuntu联网配置

物联网设计竞赛_2_Ubuntu联网配置

采用nat配置 随便定义一个VMnet虚拟网络接口&#xff0c;定义成nat模式 如果主机用的校园网&#xff0c;那么虚拟机发送消息将通过nat转换&#xff0c;转换成用户校园网ip进行发送&#xff0c;发送到校园网路由器再经过nat转换成公网ip访问互联网 点击NAT设置和DHCP设置记录好…
阅读更多...
【Mac】Perfectly Clear Workbench（智能图像清晰修复软件）安装教程

【Mac】Perfectly Clear Workbench（智能图像清晰修复软件）安装教程

软件介绍 Perfectly Clear Workbench是由Athentech Imaging开发的一款图像处理软件&#xff0c;旨在帮助用户快速、轻松地优化和改善数字照片的质量。以下是Perfectly Clear Workbench的一些主要特点和功能&#xff1a; 1.自动图像优化 该软件采用先进的图像处理算法&#xf…
阅读更多...
2024年如何选什么版本FL Studio才适合自己编曲？

2024年如何选什么版本FL Studio才适合自己编曲？

fl studio是什么软件 水果编曲软件 FL Studio&#xff0c;全称为Fruity Loops Studio&#xff0c;是一款全能音乐制作环境或数字音频工作站&#xff08;DAW&#xff09;&#xff0c;集编曲、录音、剪辑、混音等多种功能于一身。 FL Studio最初名为Fruity Loops&#xff0c;因…
阅读更多...
APP 脱壳处理

APP 脱壳处理

前言 一&#xff0c;加壳的原理 二&#xff0c;壳的分类 三&#xff0c;脱壳实践 3.1 一代壳&#xff1a;frida-dexdump 安装&#xff1a; pip install frida-dexdump运行&#xff1a; frida-dexdump -U -f com.jiuxianapk.ui这里的 com.jiuxianapk.ui 就是app的包名&#xf…
阅读更多...
[Algorithm][回溯][全排列][子集] + 回溯原理 详细讲解

[Algorithm][回溯][全排列][子集] + 回溯原理 详细讲解

目录 0.原理讲解1.全排列1.题目链接2.算法原理详解3.代码实现 2.子集1.题目链接2.算法原理详解3.代码实现 0.原理讲解 回溯算法通常⽤于解决组合问题、排列问题和搜索问题等回溯算法的基本思想&#xff1a; 从⼀个初始状态开始&#xff0c;按照⼀定的规则向前搜索&#xff0c;…
阅读更多...
14.CAS原理

14.CAS原理

文章目录 CAS原理1.什么是CAS2.Unsafe类中的CAS方法2.1.获取UnSafe实例2.2.调用UnSafe提供的CAS方法2.3.调用Unsafe提供的偏移量相关2.4.CAS无锁编程2.4.1.使用cas进行无锁安全自增案例 CAS原理 由于JVM的synchronized重量级锁设计操作系统内核态下的互斥锁的使用&#xff0c;其…
阅读更多...
【CSP CCF记录】202112-1 序列查询

【CSP CCF记录】202112-1 序列查询

题目 过程 第一次提交 暴力求解&#xff0c;运行超时&#xff0c;50分 #include<bits/stdc.h> using namespace std; int n,N; int main() {cin>>n>>N;int A[n1];A[0]0;for(int i1;i<n;i){cin>>A[i];}int f[N];int sum0;for(int i0;i<N;i){fo…
阅读更多...
HCIP-Datacom-ARST自选题库_07_割接【35道题】

HCIP-Datacom-ARST自选题库_07_割接【35道题】

一、单选题 1.在割接的测试阶段&#xff0c;符合以下哪一种情况的可以判断为割接成功? 网络承载的上层应用业务测试正常 网络设备的配置查看结果正常 网络流量路径正常 路由协议运行正常 2.在割接的测试阶段中&#xff0c;表明已经完成测试的标准是: IP设备的配置查看结…
阅读更多...
Oracle 数据库

Oracle 数据库

前言 今天开始学习 Oracle 数据库&#xff0c;这是实习公司要求的&#xff0c;虽然还没开始实习&#xff0c;但是事先熟练到岗之后就不需要再花费时间学习了。有了 MySQL 的基础&#xff0c;学习 Oracle 应该问题不大&#xff0c;不过 MySQL 一些进阶的内容依然需要再精进一下。…
阅读更多...
【原创】nnUnet V1在win11下的安装与配置

【原创】nnUnet V1在win11下的安装与配置

安装之前可以先了解一下论文的主要内容&#xff0c;便于之后网络训练与推理&#xff0c;调试程序。 论文地址&#xff1a;nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation | Nature Methods 也可以从其他博客快速浏览&#xff1a…
阅读更多...
google test 使用指南

google test 使用指南

目录 测试项目 calculator.h calculator.cpp test01.cpp 创建新项目 选择Google Test 选择要测试的项目 pch.cpp 加入依赖 设为启动项目 ​编辑 运行 ​编辑 关键点 测试项目 calculator.h #ifndef __CALCULATOR_H__ #define __CALCULATOR_H__#include <i…
阅读更多...
最新文章

Copyright @ 2022~2023