二叉搜索树Ⅲ【东北大学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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

不会心理描写,神态描写怎么办?

不会心理描写&#xff0c;神态描写怎么办&#xff1f; 文学创作&#xff0c;精微之处在于心理与神态之描绘。 一、夯实基础&#xff0c;积累素材。 欲使心理与神态描写生动&#xff0c;需先厚积薄发。博览群书&#xff0c;尤重经典之作。 “读万卷书&#xff0c;行万里路。…

【使用MCP协议连接本地和远程数据——以Claude的Windows客户端为例】

本博客内容主要是如何在Windows系统上为Claude客户端&#xff08;无需开通会员&#xff09;配置模型上下文协议(Model Context Protocol, MCP)服务器。 为什么选择 MCP&#xff1f; MCP 可帮助您在 LLM 之上构建代理和复杂的工作流程。LLM 经常需要与数据和工具集成&#xff0…

React:闭包陷阱产生和解决

在 React 中&#xff0c;闭包陷阱是一个常见的问题&#xff0c;尤其是在处理异步操作、事件处理器、或是定时器时。理解闭包的工作原理以及它在 React 中如何与状态和渲染交互&#xff0c;可以帮助你避免陷入一些常见的错误。 一、闭包陷阱的产生 1、什么是闭包陷阱&#xff1…

使用xjar 对Spring-Boot JAR 包加密运行

1 Xjar 介绍 Spring Boot JAR 安全加密运行工具&#xff0c;同时支持的原生JAR。 基于对JAR包内资源的加密以及拓展ClassLoader来构建的一套程序加密启动&#xff0c;动态解密运行的方案&#xff0c;避免源码泄露或反编译。 功能特性 无需侵入代码&#xff0c;只需要把编译好的…

[LeetCode-Python版] 定长滑动窗口1(1456 / 643 / 1343 / 2090 / 2379)

思路 把问题拆解成三步&#xff1a;入-更新-出。 入&#xff1a;下标为 i 的元素进入窗口&#xff0c;更新相关统计量。如果 i<k−1 则重复第一步。更新&#xff1a;更新答案。一般是更新最大值/最小值。出&#xff1a;下标为 i−(k-1) 的元素离开窗口&#xff0c;更新相关…

【AIGC-ChatGPT进阶副业提示词】末日生存指南 2.0:疯狂科学家的荒诞智慧

引言 在这个不断变化的世界中&#xff0c;末日似乎总是lurking在角落。但是&#xff0c;亲爱的幸存者们&#xff0c;不要害怕&#xff01;因为我&#xff0c;疯狂科学家2099&#xff0c;正在这里为你们带来最新版本的末日生存指南。这不是你祖母的应急手册&#xff0c;而是一本…

Web3.0安全开发实践:探索比特币DeFi生态中的PSBT

近年来&#xff0c;部分签名比特币交易&#xff08;PSBT&#xff09;在比特币生态系统中获得了显著关注。随着如Ordinal和基于铭文的资产等创新的兴起&#xff0c;安全的多方签名和复杂交易的需求不断增加&#xff0c;这使得PSBT成为应对比特币生态不断发展中不可或缺的工具。 …

Edge Scdn防御网站怎么样?

酷盾安全Edge Scdn&#xff0c;即边缘式高防御内容分发网络&#xff0c;主要是通过分布在不同地理位置的多个节点&#xff0c;使用户能够更快地访问网站内容。同时&#xff0c;Edge Scdn通过先进的技术手段&#xff0c;提高了网上内容传输的安全性&#xff0c;防止各种网络攻击…

oracle client linux服务器安装教程

p13390677_112040_Linux-x86-64_4of7.zip 安装前&#xff0c;确认/etc/hosts文件已配置正确 cat /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhost localhost.localdomain localhost6 localhost6.localdomain6 10.2…

【前端】Jquery拍照,通过PHP将base64编码数据转换成PNG格式,并保存图像到本地

目录 一、需求 二、开发语言 三、效果 四、业务逻辑&#xff1a; 五、web端调用摄像头 六、示例代码 1、前端 2、后端 一、需求 web端使用jquery调用摄像头拍照&#xff0c;并使用PHP把base64编码转换成png格式图片&#xff0c;下载到本地。 由于js不能指定图片存储的…

腾讯云云开发 Copilot 深度探索与实战分享

个人主页&#xff1a;♡喜欢做梦 欢迎 &#x1f44d;点赞 ➕关注 ❤️收藏 &#x1f4ac;评论 目录 一、引言 二、产品介绍 三、产品体验过程 四、整体总结 五、给开发者的复用建议 六、对 AI 辅助开发的前景展望 一、引言 在当今数字化转型加速的时代&#xff0c;…

提炼关键词的力量:AI驱动下的SEO优化策略

内容概要 在当今数字化营销的环境中&#xff0c;关键词对于提升网站的可见性和流量起着至关重要的作用。企业和个人必须重视有效的关键词策略&#xff0c;以便在竞争激烈的网络市场中脱颖而出。本文将深入探讨如何利用人工智能技术来优化SEO策略&#xff0c;特别是在关键词选择…

W25Q128读写实验(一)

十二、SPI 1. IIC与SPI对比 1. IIC 是半双工通讯&#xff0c;无法同时收发信息&#xff1b;SPI 是全双工通讯&#xff0c;可以同时收发信息&#xff1b; 2. IIC 通讯协议较复杂&#xff0c;而 SPI 通讯协议较简单&#xff1b; 3. IIC 需要通过地址选择从机&#xff0c;而 SPI …

uniApp使用腾讯地图提示未添加maps模块

uniApp使用腾讯地图&#xff0c;打包提示未添加maps模块解决方案 这是报错信息&#xff0c;在标准基座运行的时候是没问题的&#xff0c;但是打包后会提示未添加&#xff0c;可以通过在mainfest里面把地图插件上腾讯地图的key更换高德地图的key&#xff0c;定位服务可以继续用腾…

【开源项目】数字孪生轨道~经典开源项目数字孪生智慧轨道——开源工程及源码

飞渡科技数字孪生轨道可视化平台&#xff0c;基于国产数字孪生引擎&#xff0c;结合物联网IOT、大数据、激光雷达等技术&#xff0c;对交通轨道进行超远距、高精度、全天侯的监测&#xff0c;集成轨道交通运营数据&#xff0c;快速准确感知目标&#xff0c;筑牢轨交运营生命线。…

【HarmonyOS之旅】DevEco Studio的安装与环境配置

目录 1 -> 下载与安装DevEco Studio 1.1 -> 运行环境要求 1.2 -> 下载和安装DevEco Studio 2 -> 配置环境变量 3 -> 配置开发环境 4 -> 开发项目准备 5 -> 实用小技巧 5.1 -> 中文插件 2 -> 简化工程目录栏 1 -> 下载与安装DevEco Stud…

Word使用分隔符实现页面部分分栏

文章目录 Word使用分隔符实现页面部分分栏分隔符使用页面设置 Word使用分隔符实现页面部分分栏 分隔符使用 word中的分隔符&#xff1a; 前面不分栏&#xff0c;后面分栏(或前面分栏&#xff0c;后面不分栏)&#xff0c;只需要在分隔位置处插入分隔符&#xff1a;“连续”即…

多协议视频监控汇聚/视频安防系统Liveweb搭建智慧园区视频管理平台

智慧园区作为现代化城市发展的重要组成部分&#xff0c;不仅承载着产业升级的使命&#xff0c;更是智慧城市建设的重要体现。随着产业园区竞争的逐渐白热化&#xff0c;将项目打造成完善的智慧园区是越来越多用户关注的内容。 然而我们往往在规划前期就开始面临众多难题&#…

PHP接入美团联盟推广

美团给的文档没有PHP的示例代码&#xff0c;下面是以Javascript示例更改的PHP代码&#xff0c;并且已经跑通 一、计算签名 签名类&#xff0c;因为接口不多&#xff0c;所以这里只写了获取请求头 class Meituan {private $APP_KEY 你的APP_KEY;private $APP_SECRET 你的APP…

ChatGPT重大更新:新增实时搜索和高级语音

12月17日消息&#xff0c;据报道&#xff0c;OpenAI开启了第八天技术分享直播&#xff0c;对ChatGPT搜索功能进行了大量更新。 此次ChatGPT新增的功能亮点纷呈。其中&#xff0c;实时搜索功能尤为引人注目。OpenAI对搜索算法进行了深度优化&#xff0c;使得用户提出问题后&…