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

数据结构实验:二叉排序树

题目描述

对应给定的一个序列可以唯一确定一棵二叉排序树。然而,一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树,都得到一样的结果。你的任务书对于输入的各种序列,判断它们是否能生成一样的二叉排序树。

输入描述

输入包含若干组测试数据。每组数据的第1行给出两个正整数N(n≤10)和L,分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列生成一颗二叉排序树。随后L行,每行给出N个元素,属于L个需要检查的序列。
简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

输出描述

对每一组需要检查的序列,如果其生成的二叉排序树跟初始序列生成的二叉排序树一样,则输出"Yes",否则输出"No"。

样例

输入
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出
Yes
No
No


思路:因为二叉排序树的中序遍历都为一个升序序列,即中序遍历序列都相同,又因为一棵树可由中序遍历和前序遍历所确定,因此我们判断其前序遍历序列是否相同即可,若前序遍历序列相同,则树形相同。

建树过程

  • 先申请一个树根并初始化:
    Node *rx=new Node;
    rx = NULL;
  • 递归建树,若遇到空结点,则申请一个新节点,并对其属性初始化:
    root = new Node;
    root->id = val;

Code:

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
struct Node {Node* left=NULL;Node* right=NULL;int id;
};
vector<int> p,q;
map<vector<int>,bool> mp;
Node* build(Node *root,int val) {if(root == NULL) {root = new Node;root->id = val;} else if(val>=root->id) root->right = build(root->right,val);else root->left = build(root->left,val);return root;
}
void work1(Node *root) {if(root == NULL) return;p.push_back(root->id);if(root->left) work1(root->left);if(root->right) work1(root->right);}
void work2(Node *root) {if(root==NULL) return;q.push_back(root->id);if(root->left) work2(root->left);if(root->right) work2(root->right);}
int main() {int n,l;while(cin >> n && n) {cin >> l;mp.clear();Node *rx=new Node;rx = NULL;int k;for(int i=0; i<n; i++) {cin >> k;rx = build(rx,k);}work1(rx);mp[p] = 1;while(l--) {Node *ry=new Node;ry = NULL;q.clear();for(int j=0; j<n; j++) {cin >> k;ry = build(ry,k);}work2(ry);mp[q]==1?puts("Yes"):puts("No");}}return 0;
}

相关文章:

数据结构实验:二叉排序树

题目描述 对应给定的一个序列可以唯一确定一棵二叉排序树。然而&#xff0c;一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树&#xff0c;都得到一样的结果。你的任务书对于输入的各种序列&#xff0c;判断它们是否…...

Java类加载流程?

Java类加载过程是指将.class文件中的字节码数据加载到内存中&#xff0c;并生成对应的Class对象的过程。Java类加载器&#xff08;ClassLoader&#xff09;负责执行这个任务。Java类加载过程主要包括以下几个步骤&#xff1a; 加载&#xff08;Loading&#xff09;&#xff1a;…...

Docker从0到1的开始【入门篇】

Docker是一种流行的容器化平台&#xff0c;它允许开发人员将应用程序及其所有依赖项打包到一个标准化的单元中&#xff0c;从而实现快速部署和可移植性。在本文中&#xff0c;我们将列出一些常用的Docker命令&#xff0c;以帮助您更好地了解和使用Docker。 1. 安装Docker 要安…...

@ResponseStatus

目录 概述&#xff1a; 用途&#xff1a; 参数&#xff1a; 注意事项&#xff1a; 自定义异常类&#xff1a; 底层原理&#xff1a; 概述&#xff1a; 在 Spring MVC 中&#xff0c;我们有很多方法来设置 HTTP 响应的状态码其中最直接的方法&#xff1a;使用 ResponseSt…...

高效加载大文件(pandas+dask)

一、仅用pd加载大文件(iterator、chunksize) 要使用Pandas进行高效加载超大文件&#xff0c;我们通常会利用其内置的分块&#xff08;chunk&#xff09;处理功能。不过&#xff0c;请注意&#xff0c;Pandas本身并不支持多线程读取文件&#xff1b;它更倾向于单线程中进行块处理…...

游戏引擎分层简介

游戏引擎分层架构&#xff08;自上而下&#xff09; 工具层&#xff08;Tool Layer&#xff09; 在一个现代游戏引擎中&#xff0c;我们最先看到的可能不是复杂的代码&#xff0c;而是各种各样的编辑器&#xff0c;利用这些编辑器&#xff0c;我们可以制作设计关卡、角色、动画…...

向爬虫而生---Redis 探究篇6<Redis的Bigkey问题介绍>

前言: 随着数据规模的增长,Redis的BigKey问题也开始显现。 BigKey问题主要指的是存储了大量数据的key,这可能给Redis的性能和可用性带来负面影响。当一个key的数据量过大时,会占用宝贵的内存资源,拖慢Redis的响应速度。此外,存储和恢复这些BigKey也会变得困难和耗时,增…...

【开源物联网平台】FastBee认证方式和MQTT主题设计

&#x1f308; 个人主页&#xff1a;帐篷Li &#x1f525; 系列专栏&#xff1a;FastBee物联网开源项目 &#x1f4aa;&#x1f3fb; 专注于简单&#xff0c;易用&#xff0c;可拓展&#xff0c;低成本商业化的AIOT物联网解决方案 目录 一、接入步骤 1.1 设备认证 1.2 设备交…...

Ubuntu Qt控制终端运行ros

文章目录 gnome-terminalQt 通过QProcess类Qt 通过system gnome-terminal 在Ubuntu中可以使用man gnome-terminal命令查看gnome-terminal的使用指南&#xff0c;也可在ubuntu manuals查看&#xff1a; NAMEgnome-terminal — 一个终端仿真应用.概要gnome-terminal [-e, --c…...

mysql 性能调优参数配置文件

########################################################################### ## my.cnf for MySQL 8.0.x # ## 本配置参考 https://imysql.com/my-cnf-wizard.html # ## 注意&#xff1a; …...

windows右键新建文件没有txt文本文档怎么办?

我碰到此问题&#xff0c;按照以下方法改了注册表&#xff0c; 重启之后就正常了&#xff08;没有注销&#xff0c;只是单纯重启&#xff09;。以下方法来自AI&#xff1a; 如果在注册表的 .txt 路径下没有找到 ShellNew 键&#xff0c;你可以尝试手动创建这个键和所需的值来恢…...

已读不回,我又玻璃心了

最近有点上火&#xff0c;3个询盘给我整我无语了&#xff0c;难道我还没修炼到家&#xff1f;玻璃心又出来作祟了&#xff1f; 客户A急火火的发我一个文件&#xff0c;需求内容ios客户端调整&#xff0c;让我按照需求给找个人处理下&#xff0c;我收到后抓紧时间摇人&#xff0…...

面试经典150题(105-107)

leetcode 150道题 计划花两个月时候刷完之未完成后转&#xff0c;今天&#xff08;第2天&#xff09;完成了3道(105-107)150 105.&#xff08;191. 位1的个数&#xff09;题目描述&#xff1a; 编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&am…...

javaWebssh药品进销存信息管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh药品进销存信息管理系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOM…...

计算机设计大赛 深度学习实现语义分割算法系统 - 机器视觉

文章目录 1 前言2 概念介绍2.1 什么是图像语义分割 3 条件随机场的深度学习模型3\. 1 多尺度特征融合 4 语义分割开发过程4.1 建立4.2 下载CamVid数据集4.3 加载CamVid图像4.4 加载CamVid像素标签图像 5 PyTorch 实现语义分割5.1 数据集准备5.2 训练基准模型5.3 损失函数5.4 归…...

Linux系统编程(六)高级IO

目录 1. 阻塞和非阻塞 IO 2. IO 多路转接&#xff08;select、poll、epoll&#xff09; 3. 存储映射 IO&#xff08;mmap&#xff09; 4. 文件锁&#xff08;fcntl、lockf、flock&#xff09; 5. 管道实例 - 池类算法 1. 阻塞和非阻塞 IO 阻塞 IO&#xff1a;会等待操作的…...

Python与FPGA——全局二值化

文章目录 前言一、Python全局128二、Python全局均值三、Python全局OTSU四、FPGA全局128总结 前言 为什么要进行图像二值化&#xff0c;rgb图像有三个通道&#xff0c;处理图像的计算量较大&#xff0c;二值化的图像极大的减少了处理图像的计算量。即便从彩色图像转成了二值化图…...

《Docker极简教程》--Docker的高级特性--Docker Compose的使用

Docker Compose是一个用于定义和运行多容器Docker应用程序的工具。它允许开发人员通过简单的YAML文件来定义应用程序的服务、网络和卷等资源&#xff0c;并使用单个命令来启动、停止和管理整个应用程序的容器。以下是关于Docker Compose的一些关键信息和优势&#xff1a; 定义…...

tidyverse去除表格中含有NA的行

在tidyverse中&#xff0c;特别是使用dplyr包&#xff0c;去除含有NA的行可以通过filter()函数结合is.na()和any()或all()函数来实现。dplyr是tidyverse的一部分&#xff0c;提供了一系列用于数据操作的函数&#xff0c;使数据处理变得更加简单和直观。 以下是一个简单的例子&…...

开源爬虫技术在金融行业市场分析中的应用与实战解析

一、项目介绍 在当今信息技术飞速发展的时代&#xff0c;数据已成为企业最宝贵的资产之一。特别是在${industry}领域&#xff0c;海量数据的获取和分析对于企业洞察市场趋势、优化产品和服务至关重要。在这样的背景下&#xff0c;爬虫技术应运而生&#xff0c;它能够高效地从互…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

若依项目部署--传统架构--未完待续

若依项目介绍 项目源码获取 #Git工具下载 dnf -y install git #若依项目获取 git clone https://gitee.com/y_project/RuoYi-Vue.git项目背景 随着企业信息化需求的增加&#xff0c;传统开发模式存在效率低&#xff0c;重复劳动多等问题。若依项目通过整合主流技术框架&…...

电脑定时关机工具推荐

软件介绍 本文介绍一款轻量级的电脑自动关机工具&#xff0c;无需安装&#xff0c;使用简单&#xff0c;可满足定时关机需求。 工具简介 这款关机助手是一款无需安装的小型软件&#xff0c;文件体积仅60KB&#xff0c;下载后可直接运行&#xff0c;无需复杂配置。 使用…...