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

二叉排序树的创建、插入、查找和删除【数据结构】

二叉排序树

  • 若它的左子树不空,则左子树上所有结点的值均小于它根结点的值。
  • 若它的右子树不空,则右子树上所有结点的值均大于它根结点的值。
  • 它的左、右树又分为⼆叉排序树

二叉排序树也叫二叉查找树、二叉搜索树

二叉排序树的创建、插入、查找和删除

创建和插入

题目描述
给出一个数据序列,建立二叉排序树,并实现插入功能。
在建立和插入操作后,都输出二叉树的先序遍历结果i

输入
第1行输入n,表示序列包含n个数据
第2行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第3行输入m,表示要插入m个数据
输入m行,每行一个要插入的数据,都是自然数且和前面的数据不等

输出
第一行输出一开始构建的二叉排序树的先序遍历结果
从第二行起,输出m行,每行输出插入一个数据到二叉排序树后的先序遍历结果
每行输出的遍历结果中,每个数据后面都带一个空格,最后一个数据也带。

输入样例1
6
22 33 55 66 11 44
3
77
50
10

输出样例1
22 11 33 55 44 66
22 11 33 55 44 66 77
22 11 33 55 44 50 66 77
22 11 10 33 55 44 50 66 77

输入样例2
6
33 55 22 66 11 44
3
25
88
50

输出样例2
33 22 11 55 44 66
33 22 11 25 55 44 66
33 22 11 25 55 44 66 88
33 22 11 25 55 44 50 66 88

#include<bits/stdc++.h>
using namespace std;
//树节点
struct tree
{int value=0;tree* left=NULL;tree* right=NULL;
};
//插入操作
tree* insert(tree* t,int a)
{tree* root=t;while(1){if(t->value==0) {t->value=a;break;}if(a<t->value) {if(!t->left) t->left=new tree;t=t->left;}else {if(!t->right) t->right=new tree;t=t->right; }}return root;
}
//先序遍历
void prior(tree* t)
{if(t==NULL) return ;cout<<t->value<<" ";prior(t->left);prior(t->right);
}
int main()
{int n;cin>>n;tree* root=new tree;for(int i=0;i<n;i++){int x;cin>>x;root=insert(root,x);}prior(root);cout<<endl;int m;cin>>m;for(int i=0;i<m;i++) {int x;cin>>x;//插入root=insert(root,x);prior(root);cout<<endl;}return 0;
}

查找

题目描述
给出一个数据序列,建立二叉排序树,并实现查找功能

输入
第1行输入n,表示首个序列包含n个数据
第2行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第3行输入m,表示要查找m个数据
接着输入m行,每行一个要查找的数据,都是自然数
以此类推输入下一个示例

输出
第一行输出有序的数据序列,对二叉排序树进行中序遍历可以得到
从第二行起,输出查找结果,如果查找成功输出查找次数,如果查找失败输出-1

输入样例1
6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

输出样例1
11 22 33 44 55 66
2
1
2
4
3
4
-1

输入样例2
6
33 22 55 11 66 44
4
88
11
44
66

输出样例2
11 22 33 44 55 66
-1
3
3
3

#include<bits/stdc++.h>
using namespace std;
//树节点
struct tree
{int value=0;tree* left=NULL;tree* right=NULL;
};
//插入
tree* insert(tree* t,int a)
{tree* root=t;while(1){if(t->value==0) {t->value=a;break;}if(a<t->value) {if(!t->left) t->left=new tree;t=t->left;}else {if(!t->right) t->right=new tree;t=t->right; }}return root;
}
//中序遍历
void middle(tree* t)
{if(t==NULL) return ;middle(t->left);cout<<t->value<<" ";middle(t->right);
}
//查找
int find(tree* t,int a,int time)
{while(1){time++;if(t->value==0){time=-1;break;}if(t->value==a) break;if(a<t->value){if(!t->left) t->left=new tree;t=t->left;}else{if(!t->right) t->right=new tree;t=t->right;}}return time;
}
int main()
{int n;cin>>n;tree* root=new tree;for(int i=0;i<n;i++){int x;cin>>x;root=insert(root,x);}middle(root);cout<<endl;int m;cin>>m;for(int i=0;i<m;i++){int x;cin>>x;cout<<find(root,x,0)<<endl;}return 0;
}

删除

题目描述
给出一个数据序列,建立二叉排序树,并实现删除功能
对二叉排序树进行中序遍历,可以得到有序的数据序列

输入
第一行输入t,表示有t个数据序列
第二行输入n,表示首个序列包含n个数据
第三行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第四行输入m,表示要删除m个数据
从第五行起,输入m行,每行一个要删除的数据,都是自然数
以此类推输入下一个示例

输出
第一行输出有序的数据序列,对二叉排序树进行中序遍历可以得到
从第二行起,输出删除第m个数据后的有序序列,输出m行
以此类推输出下一个示例的结果

输入样例1
1
6
22 33 55 66 11 44
3
66
22
77

输出样例1
11 22 33 44 55 66
11 22 33 44 55
11 33 44 55
11 33 44 55

提示
当删除数据不在序列中,那么删除操作等于不执行,所以输出序列不变化

  1. 被删除的节点是叶子节点,将双亲节点中相应的指针域的值改为空
  2. 被删除的节点只有左子树或右子树,将要删除的节点的双亲节点相应指针域的值指向被删除节点的左子树或者右子树
  3. 被删除节点既有左子树又有右子树,将左子树中的最大值或者右子树中的最小值代替该节点
#include<bits/stdc++.h>
using namespace std;
//树节点
struct tree
{int value=0;tree* left=NULL;tree* right=NULL;
};
//插入
tree* insert(tree* t,int a)
{tree* root=t;while(1){if(t->value==0) {t->value=a;break;}if(a<t->value) {if(!t->left) t->left=new tree;t=t->left;}else {if(!t->right) t->right=new tree;t=t->right; }}return root;
}
//中序遍历
void middle(tree* t)
{if(t==NULL||t->value==0) return ;middle(t->left);cout<<t->value<<" ";middle(t->right);
}
//删除
void del(tree* t,int a)
{//记录父节点tree* p=NULL;while(1){if(t->value==0) break;if(t->value==a){//叶子结点直接删除if(!t->left&&!t->right){if(p->left==t) p->left=NULL;else p->right=NULL;break;}//只有左子树或只有右子树if(!t->left||!t->right){//左子树不空if(t->left){if(p->left==t) p->left=t->left;else p->right=t->left;break;}//右子树不空if(t->right){if(p->left==t) p->left=t->right;else p->right=t->right;break;}}//左右子树都不空//本做法是用左子树最大值代替该节点值tree* now=t->left;tree* par=t;while(now->right) {par=now;now=now->right;}//左子树最大值int value=now->value;//更新值t->value=value;//这里注意!!!if(!now->left&&!now->right) {//直接删除左子树的根节点if(par==t) par->left=NULL;//删除的不是左子树的根节点else par->right=NULL;}//有子节点肯定是左子节点else par->right=now->left;break;}if(a<t->value){if(!t->left) t->left=new tree;p=t;t=t->left;}else{if(!t->right) t->right=new tree;p=t;t=t->right;}}
}
int main()
{int t;cin>>t;for(int i=0;i<t;i++){int n;cin>>n;tree* root=new tree;for(int i=0;i<n;i++){int x;cin>>x;root=insert(root,x);}middle(root);cout<<endl;int m;cin>>m;for(int i=0;i<m;i++) {int x;cin>>x;del(root,x);middle(root);cout<<endl;}}return 0;
}

相关文章:

二叉排序树的创建、插入、查找和删除【数据结构】

二叉排序树 若它的左子树不空&#xff0c;则左子树上所有结点的值均小于它根结点的值。若它的右子树不空&#xff0c;则右子树上所有结点的值均大于它根结点的值。它的左、右树又分为⼆叉排序树 二叉排序树也叫二叉查找树、二叉搜索树 二叉排序树的创建、插入、查找和删除 …...

【管理篇 / 恢复】❀ 07. macOS下用命令刷新固件 ❀ FortiGate 防火墙

【简介】随着苹果电脑的普及&#xff0c;很多管理员都会通过苹果电脑对飞塔防火墙进行管理。当防火墙需要命令状态下刷新固件时&#xff0c;在macOS下用命令刷新固件&#xff0c;将会是一个小小的挑战。 首先是硬件的连接&#xff0c;USB配置线的USB一头&#xff0c;接入MAC的U…...

工作纪实40-使用redis的几种姿势

线上查问题看某个redis的key值&#xff0c;记录一下 1.直接使用telnet进行连接&#xff08;贼拉方便&#xff09; telnet ip port > auth pwd1.模糊查询 scan 0 MATCH abc* 2.查看所有key keys * 3.ttl key 查看key的ttl2.使用redis-cli连接(费劲吧啦&#xff0c;还需要本地…...

修改 docker /dev/shm 的大小

修改 docker /dev/shm 的大小 1&#xff0c;获取完整id&#xff1a; docker inspect 245| grep Id rootlynxi:~# docker inspect 245| grep Id"Id": "245ab167ed9a79873b31b3a38df2053870fe72f267c3c1a660df25c63e37e88b",2&#xff0c;修改 ShmSize&…...

【观察】Aginode安捷诺:坚守“长期主义”,服务中国数字经济

毫无疑问&#xff0c;随着整个社会加速数字化转型&#xff0c;尤其是5G、人工智能、大数据等技术兴起&#xff0c;以及智慧医疗、智慧金融、智能制造等应用加速落地&#xff0c;算力网络在经济社会发展中扮演了愈来愈重要的角色&#xff0c;成为支撑数字经济蓬勃发展的“新引擎…...

HttpClient库与代理IP在爬虫程序中的应用

目录 前言 一、HttpClient库的基本使用方法 二、代理IP的使用方法 三、代理IP池的使用方法 四、总结 前言 在编写爬虫程序时&#xff0c;我们经常会使用HttpClient库来发送HTTP请求&#xff0c;获取网页内容。然而&#xff0c;有些网站可能会对频繁的请求进行限制&#x…...

C#最佳工具集合:IDE、分析、自动化工具等

C#是企业中广泛使用的编程语言&#xff0c;特别是那些依赖微软的程序语言。如果您使用C#构建应用程序&#xff0c;则最有可能使用Visual Studio&#xff0c;并且已经寻找了一些扩展来对您的开发进行管理。但是&#xff0c;这个工具列表可能会改变您编写C#代码的方式。 C#编程的…...

promethues grafana 安装和使用

文章目录 1、promethues安装2、node-exporter安装3、grafana安装4、配置promethues监控node节点5、grafana操作外传 Docker 镜像下载地址&#xff1a; https://hub.docker.com 比较好的hub.docker.com///-- https://hub.docker.com/u/bitnami grafana监控面板&#xff1a;https…...

华为DriveONE电机控制器拆解实拍

如果说之前的问界M5、M7&#xff0c;华为让我们看到其在智能化上确实拥有遥遥领先的能力&#xff0c;那么在智界S7上&#xff0c;则让我们看到华为在动力、底盘这些硬件执行层面&#xff0c;竟然也有不输给很多车企的实力。1、华为电驱&#xff0c;全球第一&#xff1f;在智界S…...

【git使用】历史commit的分割(git rebase和 git reset的联合使用)

参考 [译] 分割一个已存在的 git commit - 掘金Git - 重写历史idea git如何撤回提交 - PingCodegit 工作原理与撤销操作图解 | Shall We Code? 分割一个已存在的 git commit Git 与其他版本控制系统的主要区别之一&#xff0c;在于其允许用户重写历史。实现这一目的的主要途…...

栈和队列oj题——225. 用队列实现栈

** 个人主页&#xff1a;晓风飞 专栏&#xff1a; 数据结构| Linux|| C语言 路漫漫其修远兮&#xff0c;吾将上下而求索 文章目录 题目要求&#xff1a;实现 MyStack 类&#xff1a;注意&#xff1a;示例&#xff1a;解释&#xff1a;提示&#xff1a; 解题核心数据结构的定义初…...

集合的三种遍历方式

迭代器&#xff08;Iterator&#xff09; 概述&#xff1a;Iterator 是个接口&#xff0c;迭代器是集合的专用遍历方式 使用方法&#xff0c;我们想要使用迭代器&#xff0c;必须首先得到集合对象&#xff0c;通过集合对象生成迭代器对象&#xff0c;才能进行集合的遍历 常用…...

Mysql 中的常用命令

在数字化世界中&#xff0c;数据库已经成为数据存储和处理的核心。而MySQL&#xff0c;作为最受欢迎的关系型数据库管理系统之一&#xff0c;其强大的功能和易用性使它成为开发者和企业的首选。掌握MySQL中的常用命令&#xff0c;是每一位数据库管理员和开发者的基本要求。本篇…...

【Java】CompletableFuture使用方法

背景 CompletableFuture是Java 8中引入的一个类&#xff0c;它实现了Future和CompletionStage接口&#xff0c;用于表示异步计算的结果。使用CompletableFuture可以方便地编写异步编程的代码&#xff0c;并且可以链式地组合多个异步操作。 接口 CompletableFuture实现了Future…...

摆烂式学习ssh

摆烂式学习ssh ssh工作原理ssh基本使用sshd配置文件密钥登录1.客户端2.服务器3.注意事项4.使用密钥登录测试 ssh高级使用技巧1.在非正规端口启动2.rsync 命令3.透过 ssh 通道加密原本无加密的服务4.以ssh信道配合x server 传递图形接口5.ssh配合virtualbox虚拟机使用技巧 ssh工…...

用 Python 抓取 bilibili 弹幕并分析!

01 实现思路 首先&#xff0c;利用哔哩哔哩的弹幕接口&#xff0c;把数据保存到本地。接着&#xff0c;对数据进行分词。最后&#xff0c;做了评论的可视化。 02 弹幕数据 平常我们在看视频时&#xff0c;弹幕是出现在视频上的。实际上在网页中&#xff0c;弹幕是被隐藏在源代码…...

目标检测YOLO实战应用案例100讲-基于红外图像处理的无人机光伏组件故障检测(续)

目录 3.2 自适应温度阈值故障检测算法设计 3.3 基于拟合灰度曲线的故障检测方案设计...

go mod 命令详解

文章目录 1.关于模块2.关于 go mod3.格式4.示例参考文献 1.关于模块 模块&#xff08;Modules&#xff09;是 Go 1.11 版本引入的一依赖管理机制。 一个模块是 Go packages 的集合&#xff0c;定义在项目根目录下的 go.mod 文件。go.mod 文件定义了模块的路径&#xff0c;这也…...

花了一小时,拿python手搓了一个考研背单词软件

听说没有好用的电脑端背单词软件&#xff1f;只好麻烦一下&#xff0c;花了一小时&#xff0c;拿python手搓了一个考研背单词软件。 代码已经开源在我的github上&#xff0c;欢迎大家STAR&#xff01; 其中&#xff0c;数据是存放在sqlite中&#xff0c;形近词跳转是根据jaro …...

一篇文章学会Vim

一篇文章学会Vim 声明&#xff1a;以下内容均为我个人的理解&#xff0c;如果发现错误或者疑问可以联系我共同探讨 简介 Vim是一个高度可定制的终端文本编辑器&#xff0c;它可以很方便的创建和修改任何类型的文本。作为vi的升级版&#xff0c;有许多新的特性(以下列出的特性…...

面试算法91:粉刷房子

题目 一排n幢房子要粉刷成红色、绿色和蓝色&#xff0c;不同房子被粉刷成不同颜色的成本不同。用一个n3的数组表示n幢房子分别用3种颜色粉刷的成本。要求任意相邻的两幢房子的颜色都不一样&#xff0c;请计算粉刷这n幢房子的最少成本。例如&#xff0c;粉刷3幢房子的成本分别为…...

js逆向第11例:猿人学第4题雪碧图、样式干扰

任务4:采集这5页的全部数字,计算加和并提交结果 打开控制台查看请求地址https://match.yuanrenxue.cn/api/match/4,返回的是一段html网页代码 复制出来格式化后,查看具体内容如下: <td><img src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABUAAA…...

OpenEular23.09(欧拉)操作系统为企业搭建独立的K8S集群环境,详细流程+截图

一.环境&#xff1b; win10&#xff0c;vmware16 pro&#xff0c;openeular23.09&#xff0c;linux内核 6.4.0-10.1.0.20.oe2309.x86_64&#xff0c; docker-engine 2:18.09.0-328&#xff0c;kubernetes 1.25.3&#xff0c;containerd 1.6.22&#xff0c;calico v3.25 集群…...

学生成绩管理系统半成品

C语言的老师在给我们讲指针的时候&#xff0c;讲的并不深入&#xff0c;她用了一个学生成绩管理系统来引入指针这个东西并给我们讲解&#xff0c;但我觉得她的管理系统功能有一些不足&#xff0c;并且不是很美观&#xff0c;所以说心血来潮&#xff0c;自己也动手写了一个学生成…...

国家信息安全水平等级考试NISP二级题目卷⑤(包含答案)

国家信息安全水平等级考试NISP二级题目卷&#xff08;五&#xff09; 国家信息安全水平等级考试NISP二级题目卷&#xff08;五&#xff09;需要报考咨询可以私信博主&#xff01; 前言&#xff1a; 国家信息安全水平考试(NISP)二级&#xff0c;被称为校园版”CISP”,由中国信息…...

4.快速实现增删改查,模糊查询功能

打开springboot项目&#xff0c;在com.example下建包common,在common下新建Result.java 4.1封装统一的返回数据结构 1.在Result.java中编写如下代码&#xff1a; private static final String *SUCCESS*"0"; private static final String *ERROR*"-1"; p…...

【Redux】自己动手实现redux和react-redux

1. React提供context的作用 在class组件的世界里&#xff0c;如果后代组件共享某些状态&#xff0c;比如主题色、语言键&#xff0c;则需要将这些状态提升到根组件&#xff0c;以props的方式从根组件向后代组件一层一层传递&#xff0c;这样则需要在每层写props.someData&#…...

代码随想录算法训练营day6|242.有效的字母异位词、349.两个数组的交集、202.快乐数

哈希表理论基础 建议&#xff1a;大家要了解哈希表的内部实现原理&#xff0c;哈希函数&#xff0c;哈希碰撞&#xff0c;以及常见哈希表的区别&#xff0c;数组&#xff0c;set 和map。 什么时候想到用哈希法&#xff0c;当我们遇到了要快速判断一个元素是否出现集合里的时…...

2024.1.4每日一题

LeetCode每日一题 2397.被列覆盖的最多行数 2397. 被列覆盖的最多行数 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix &#xff1b;另给你一个整数 numSelect&#xff0c;表示你必须从 matrix 中选择的 不同 …...

C++协程和线程的区别?详细介绍一下C++协程

C协程和线程的区别 线程是操作系统级别的资源&#xff0c;由操作系统负责调度和切换&#xff0c;每个线程都有自己的堆栈和执行上下文。线程之间的切换需要保存和恢复线程的执行上下文&#xff0c;这个过程有一定的开销。协程是用户态的轻量级线程&#xff0c;协程的调度完全由…...

景观建设网站/百度seo关键词怎么做

目录消息方法消息处理消息宏消息机制回调函数一个好的验证系统应该具有的消息管理特性&#xff1a; 通过一种标准化的方式打印信息&#xff1b;过滤&#xff08;重要级别&#xff09;信息&#xff1b;打印通道。 这些特性在UVM中均有支持。UVM提供了一系列丰富的类和方法来生…...

网站欢迎页面在线设计/人民网 疫情

一、环境准备 1、准备三台服务器 192.168.123.103 master 192.168.123.104 data1 192.168.123.105 data2 2、更改服务器hosts #vim /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhost local…...

dede做双语网站/制作网页用什么软件

var sResult ""; $(function () {//生成验证码var context $("#myCanvas")[0].getContext("2d"); //canvas的获取必须用DOM方式获取&#xff0c;所以必须把jQuery方式转换成DOM方式context.font "50px 微软雅黑"; //常用字体为微软…...

求生之路2怎么做非官方网站/广州网站优化公司排名

题意&#xff1a;中文题&#xff0c;就不解释了。 题解&#xff1a;代码就像女生的裙子&#xff0c;越短看着越性感~~当我们选定树根&#xff0c;那么与他相邻为1的边最后一定会翻转奇数次才能变为0&#xff0c;与他相邻为偶数的边&#xff0c;最后一定翻转偶数次&#xff0c;所…...

温江建设局备案网站/如何进行搜索引擎优化 简答案

cdn引入(正常) 通过cdn方式引入是不会报错的。 src引入&#xff08;报错&#xff09; 然后我用npm下载了bootstrap和jquery&#xff0c;使用src方式引入居然报错了。 原因 当引入jQuery和bootstrap文件时会报错的原因是&#xff1a;electron 的 Renderer 端因为注入了 No…...

同一个域名可以做几个网站吗/seo网站关键词排名提升

最近在做一个分类的任务&#xff0c;输入为3通道车型图片&#xff0c;输出要求将这些图片对车型进行分类&#xff0c;最后分类类别总共是30个。 开始是试用了实验室师姐的方法采用了VGGNet的模型对车型进行分类&#xff0c;据之前得实验结果是训练后最高能达到92%的正确率&…...