当前位置: 首页 > news >正文

二叉搜索树Ⅲ【东北大学oj数据结构8-3】C++

二叉搜索树 III
B:在二叉搜索树II中加入delete指令,创建程序对二叉搜索树T执行如下指令。

插入 k:将key k 插入到 T 中。
find k:报告T中是否存在key k。
delete k:删除key为 k 的节点。
打印:使用中序树遍历和先序树遍历算法打印key值。
删除 k,删除二叉搜索树 T 给定的键为 k 的节点 z,更新父子链接(指针),同时根据考虑以下三种情况的算法保持二叉搜索树条件:

如果 z 没有孩子,则删除 z 的父母 p 的孩子(即 z)。
如果 z 只有一个孩子,将 z 的父节点的子节点更改为 z 的子节点,将 z 的子节点的父节点更改为 z 的父节点,然后从树中删除 z。
如果 z 有两个孩子,则将 z 的下一个节点 y 的key复制到 z 的key并删除 y。这里z的下一个节点是中间前向巡逻中z之后得到的节点。

输入
输入的第一行给出了指令数 m。在下一个 m 行,以插入 k、查找 k、删除 k 或打印的形式在一行上给出指令。

输出
对于每个 find k 指令,如果 T 包含 k 则输出 yes,如果 T 不包含则输出 no。
进一步,对于每条打印指令,将中序遍历算法和先序遍历算法得到的key的排列输出到一行。在每个key之前打印一个空格。

约束
指令数不超过50万条。
打印指令数量不超过10条。
−2,000,000,000 ≤ key ≤ 2,000,000,000
如果按照上面的伪代码算法,树的高度不会超过100。
二叉搜索树中的键没有重复。

数据结构

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

输出样例

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22 

#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;// 定义树的节点结构
struct Node {int key;Node* right;Node* left;Node* p;
};Node* creat(int a)
{Node* n=new Node();n->key=a;n->left=nullptr;n->right=nullptr;n->p=nullptr;return n;
}Node* insertt(Node* root,Node* z)
{Node* y=nullptr;Node* x=root;while(x!=nullptr){y=x;if(z->key<x->key)x=x->left;elsex=x->right;}z->p=y;if(y==nullptr)root=z;else if(z->key<y->key)y->left=z;elsey->right=z;return root;
}Node* findd(Node* root,int k)
{while(root!=nullptr&&k!=root->key){if(k<root->key)root=root->left;elseroot=root->right;}return root;
}Node* deletee(Node* root,Node* z)
{if(z->left==nullptr&&z->right==nullptr){if(z->p==nullptr){delete z;return nullptr;}if(z->p->left==z)z->p->left=nullptr;elsez->p->right=nullptr;delete z;}else if(z->left==nullptr||z->right==nullptr){Node* child=(z->left!=nullptr)?z->left:z->right;if(z->p==nullptr){delete z;return child;}if(z->p->left==z)z->p->left=child;elsez->p->right=child;child->p=z->p;delete z;}else{Node* y=z->right;while(y->left!=nullptr){y=y->left;}z->key=y->key;root=deletee(root,y);}return root;
}void preorder(Node* a)
{if(a==nullptr) return;cout<<a->key<<" ";preorder(a->left);preorder(a->right);
}
void inorder(Node* a)
{if(a==nullptr) return;inorder(a->left);cout<<a->key<<" ";inorder(a->right);
}int main() {int n;Node* tree=nullptr;cin>>n;for (int i = 0; i < n; i++) {string c;cin>>c;if(c=="insert"){int v;cin>>v;Node* newNode=creat(v);tree=insertt(tree,newNode);}if(c=="find"){int v;cin>>v;Node* a=findd(tree,v);if(a)cout<<"yes"<<endl;elsecout<<"no"<<endl;}if(c=="delete"){int v;cin>>v;Node* a=findd(tree,v);if(a)tree=deletee(tree,a);}if(c=="print"){inorder(tree);cout<<endl;preorder(tree);cout<<endl;}}return 0;
}

相关文章:

二叉搜索树Ⅲ【东北大学oj数据结构8-3】C++

二叉搜索树 III B&#xff1a;在二叉搜索树II中加入delete指令&#xff0c;创建程序对二叉搜索树T执行如下指令。 插入 k&#xff1a;将key k 插入到 T 中。 find k&#xff1a;报告T中是否存在key k。 delete k&#xff1a;删除key为 k 的节点。 打印&#xff1a;使用中序树遍…...

【面试笔记】CPU 缓存机制

CPU 缓存机制 1. CPU Cache 与 MMU1.1 MMU 是什么&#xff1f;TLB 又是什么&#xff1f;他们是怎么工作的&#xff1f;2.2 简述 Cache 与 MMU 的协作关系&#xff1f;2.3 简述 Cache 与 MMU 的协作工作流程&#xff1f; 2. CPU 多层次缓存2.1 什么是 CPU 的多层次缓存结构&…...

MySQL基础函数使用

目录 简介 1. 单行函数 1.1 字符串函数 1.2 日期函数 1.3 数值函数 1.4 转换函数 1.5 其他函数 2. 多行函数 示例&#xff1a; 3. 数据分组 示例&#xff1a; 4. DQL单表关键字执行顺序 示例&#xff1a; 5. 多表查询 示例&#xff1a; 6. 表与表的外连接 示例…...

解决docker环境下aspose-words转换word成pdf后乱码问题

描述 环境&#xff1a;docker 部署工具&#xff1a;Jenkins 需求&#xff1a;本地上传的word文档需要转换成pdf 问题&#xff1a;转换之后的pdf文档出现小框框&#xff08;乱码&#xff09; 转换成PDF的操作 pom&#xff1a; <dependency><groupId>org.apach…...

C# 生成随机数的方法

C# 提供了一种强大而方便的工具类 Random &#xff0c;用于生成随机数。这里将分类讨论如何通过 C# 实现随机数生成&#xff0c;以及应用于实际情况中的一些具体方案。 一、Random 类概述 Random 类表示一个伪随机数生成器&#xff0c;用于生成满足随机性统计要求的数字序列。…...

ip_done

文章目录 路由结论 IP分片 数据链路层重谈Mac地址MAC帧报头局域网的通信原理MSS&#xff0c;以及MAC帧对上层的影响ARP协议 1.公司是不是这样呢? 类似的要给运营商交钱&#xff0c;构建公司的子网&#xff0c;具有公司级别的入口路由器 2&#xff0e;为什么要这样呢?? IP地…...

3D可视化引擎HOOPS Visualize与HOOPS Luminate Bridge的功能与应用

HOOPS Visualize HPS / HOOPS Luminate Bridge为开发者提供了强大的工具&#xff0c;用于在CAD应用中集成逼真的渲染能力。本文旨在梳理该桥接产品的核心功能、使用方法及应用场景&#xff0c;为用户快速上手并充分利用产品特性提供指导。 桥接产品的核心功能概述 HOOPS Lumi…...

Docder 搭建Redis分片集群 散片插槽 数据分片 故障转移 Java连接

介绍 使多个 Redis 实例共同工作&#xff0c;实现数据的水平扩展。通过将数据分片到多个节点上&#xff0c;Redis 集群能够在不牺牲性能的前提下扩展存储容量和处理能力&#xff0c;从而支持更高并发的请求。Redis 集群不仅支持数据分片&#xff0c;还提供了自动故障转移和高可…...

校园交友app/校园资源共享小程序/校园圈子集合二手物品交易论坛、交友等综合型生活服务社交论坛

多客校园社交圈子系统搭建 校园交友多功能系统源码: 1、更改学校为独立的模块。整体UI改为绿色&#xff0c;青春色&#xff0c;更贴近校园风格。2、圈子归纳到学校去进行运营。每个学校可建立多个圈子。和其他学校圈子互不干扰。3、增加用户绑定学校&#xff0c;以后进入将默认…...

Chaos Mesh云原生的混沌测试平台搭建

Chaos Mesh云原生的混沌测试平台搭建 一.环境准备 ​ 确认已经安装helm&#xff0c;如要查看 Helm 是否已经安装&#xff0c;请执行如下命令&#xff1a; helm version二.使用helm安装 1.添加 Chaos Mesh 仓库 ​ 在 Helm 仓库中添加 Chaos Mesh 仓库&#xff1a; helm re…...

Vue3之组合式API详解

Vue 3引入了一种新的API风格——组合式API&#xff08;Composition API&#xff09;&#xff0c;旨在提升组件的逻辑复用性和可维护性。本文将详细阐述Vue 3中的组合式API&#xff0c;包括其定义、特点、使用场景、优势等&#xff0c;并给出具体的示例代码。 一、定义 组合式…...

大模型的构建与部署(3)——数据标注

版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl1. 数据标注的重要性 1.1 增强数据可解释性 数据标注通过为原始数据添加标签或注释,显著增强了数据的可解释性。在机器学习和深度学习领域,模型的训练依赖于大量带标签的数据。这些标签不仅帮助…...

AI发展与LabVIEW程序员就业

人工智能&#xff08;AI&#xff09;技术的快速发展确实对许多行业带来了变革&#xff0c;包括自动化、数据分析、软件开发等领域。对于LabVIEW程序员来说&#xff0c;AI的崛起确实引发了一个值得关注的问题&#xff1a;AI会不会取代他们的工作&#xff0c;导致大量失业&#x…...

本地事务 + 消息队列事务方案设计

Spring Boot 和 RocketMQ 在Spring Boot项目中实现“本地事务 消息队列事务”的方案&#xff0c;可以按照以下步骤实现&#xff1a; 先执行MySQL本地事务操作&#xff08;未提交&#xff09;随后发送消息到消息队列&#xff08;如RocketMQ事务消息&#xff09;等待消息队列确…...

pinctrl子系统学习笔记

一、背景 cpu的gpio引脚可以复用成多个功能&#xff0c;如可以配置成I2C或者普通GPIO模式。配置方式一般是通过写引脚复用的配置寄存器&#xff0c;但是不同芯片厂商配置寄存器格式内容各不相同&#xff0c;设置引脚复用无法做到通用且自由的配置&#xff0c;只能在启动初始化…...

使用vue-element 的计数器inputNumber,传第三个参数

使用vue-element 的计数器inputNumber。 其中的change 事件中&#xff0c;默认自带两个参数&#xff0c;currentValue和oldValue&#xff0c;分别代表改变后的数和改变前的数&#xff0c; 如果想要传第三个参数&#xff0c; change"(currentValue, oldValue) > numCha…...

如何从0构建一个flask项目,直接上实操!!!

项目结构 首先&#xff0c;创建一个项目目录&#xff0c;结构如下&#xff1a; flask_app/ │ ├── app.py # Flask 应用代码 ├── static/ # 存放静态文件&#xff08;如CSS、JS、图片等&#xff09; │ └── style.css # 示例…...

Mongoose连接数据库操作实践

文章目录 介绍特点&#xff1a;Mongoose 使用&#xff1a;创建项目并安装&#xff1a;连接到 MongoDB&#xff1a;定义 Schema&#xff1a;创建模型并操作数据库&#xff1a;创建文档&#xff1a;查询文档&#xff1a;更新文档&#xff1a;删除文档&#xff1a;使用钩子&#x…...

centos 7.9 freeswitch1.10.9环境搭建

亲测版本centos 7.9系统–》 freeswitch1.10.9 一、下载插件 yum install -y git alsa-lib-devel autoconf automake bison broadvoice-devel bzip2 curl-devel libdb4-devel e2fsprogs-devel erlang flite-devel g722_1-devel gcc-c++ gdbm-devel gnutls-devel ilbc2...

Gitlab服务管理和仓库项目权限管理

Gitlab服务管理 gitlab-ctl start # 启动所有 gitlab 组件&#xff1b; gitlab-ctl stop # 停止所有 gitlab 组件&#xff1b; gitlab-ctl restart # 重启所有 gitlab 组件&#xff1b; gitlab-ctl status …...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...