当前位置: 首页 > 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 …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...