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

【中等】保研/考研408机试-二叉树相关

目录

一、基本二叉树

1.1结构

1.2前序遍历(注意三种遍历中Visit所在的位置)

1.2中序遍历

1.3后序遍历

二、真题实战

2.1KY11 二叉树遍历(清华大学复试上机题)【较难】

2.2KY212 二叉树遍历二叉树遍历(华中科技大学复试题)【中等】


一、基本二叉树

1.1结构

首先定义二叉树的结构

struct TreeNode{//数据类型 变量;char data;TreeNode *leftChild;  //左子树 TreeNode *rightChild; //右子树 TreeNode(char x) : data(x), leftChild(NULL), rightChild(NULL) {}
};

 关于建树,看玩遍历后看题解。

1.2前序遍历(注意三种遍历中Visit所在的位置

Visit是访问格式,比如print输出,不一定是函数

访问根节点-左子树-右子树,遍历过程可以想成逆时针。如图所示。

void PreOrder(TreeNode* root){if(root==NULL){return;}Visit(root->data);PreOrder(root->leftChild);PreOrder(root->rightChild);return ;
}

1.2中序遍历

左-中-右

void InOrder(TreeNode* root){if(root==NULL){return ;}InOrder(root->leftChild);Visit(root->data);InOrder(root->rightChild);return ;
}

1.3后序遍历

左-右-根

void PostOrder(TreeNode* root){if(root==NULL){return ;}PostOrder(root->leftChild);PostOrder(root->rightChild);Visit(root->data);return ;
}

1.4层次遍历

暂时没有遇到,先不更,需要用到 队列辅助更新。

二、真题实战

2.1KY11 二叉树遍历(清华大学复试上机题)【较难】

二叉树遍历_牛客题霸_牛客网

描述

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

输入描述:

输入包括1行字符串,长度不超过100。

输出描述:

可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。

示例1

输入:

abc##de#g##f###

复制输出:

c b e g d f a 

总结:注意建立树的顺序和所需变量,root->leftChild或者root->rightChild的赋值。异常情况返回NULL,以及最后返回root。整体就是:确定结构-建树方法-遍历方法-主程序。

#include <bits/stdc++.h>
using namespace std;
struct TreeNode{//数据类型 变量;char data;TreeNode *leftChild;  //左子树 TreeNode *rightChild; //右子树 TreeNode(char x) : data(x), leftChild(NULL), rightChild(NULL) {}
};//建树 先序遍历 中-左-右 
TreeNode* PreBuild(int& index,string s ){char c=s[index];index++;if(c=='#'){return NULL;}TreeNode* root=new TreeNode(c);root->leftChild=PreBuild(index,s);root->rightChild=PreBuild(index,s);return root;
}void InOrder(TreeNode* root){if(root==NULL){return ;}InOrder(root->leftChild);cout<<root->data<<" ";InOrder(root->rightChild);return ;
}int main() {string s;while(cin>>s){int index=0;TreeNode* root=PreBuild(index,s);InOrder(root);}return 0;
}

2.2KY212 二叉树遍历二叉树遍历(华中科技大学复试题)【中等】

二叉树遍历_牛客题霸_牛客网

描述

二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入描述:

两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。

输出描述:

输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。

示例1

输入:

ABC
BAC
FDXEAG
XDEFAG

复制输出:

BCA
XEDGAF

总结:我感觉这个建树比上一个难许多,整道题就是考察建树。

根据先序遍历的性质,第一个节点就是根节点,根据这个入手。(做题时一定要结合数据结构的特性) 

再根据中序遍历的性质,找到根节点索引位置的话,左边的就是左子树,右边的就是右子树。再递归处理。

这个根节点索引位置前序遍历字符串中序遍历字符串都能用,都是分块节点。

递归停止的标志就是先序遍历字符串长度为0,返回NULL(空节点)

函数解释:sub = str.substr(7, 5); // 从索引为7的位置提取长度为5的子字符串

sub = str.substr(7);代表从索引7开始到末尾的所有字符串 。

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c):data(c),leftChild(NULL),rightChild(NULL){}
};
TreeNode* Build(string s1,string s2){if(s1.size()==0){return NULL;}char c=s1[0];TreeNode* root=new TreeNode(c);int index=s2.find(c);root->leftChild=Build(s1.substr(1,index),s2.substr(0,index));root->rightChild=Build(s1.substr(index+1),s2.substr(index+1));return root; 
}void PostOrder(TreeNode* root){if(root==NULL){return;}PostOrder(root->leftChild);PostOrder(root->rightChild);cout<<root->data;return ;
}int main() 
{string s1,s2,s3,s4;cin>>s1>>s2>>s3>>s4;TreeNode* root=Build(s1,s2);PostOrder(root);cout<<endl;TreeNode* root2=Build(s3,s4);PostOrder(root2);return 0;
}

相关文章:

【中等】保研/考研408机试-二叉树相关

目录 一、基本二叉树 1.1结构 1.2前序遍历&#xff08;注意三种遍历中Visit所在的位置&#xff09; 1.2中序遍历 1.3后序遍历 二、真题实战 2.1KY11 二叉树遍历&#xff08;清华大学复试上机题&#xff09;【较难】 2.2KY212 二叉树遍历二叉树遍历&#xff08;华中科技大…...

自动驾驶---Motion Planning之构建SLT Driving Corridor

1 背景 在上篇博客《自动驾驶---Motion Planning之Speed Boundary》中,主要介绍了Apollo中Speed Boundary的一些内容,可以构造ST图得到边界信息,最后结合粗糙的速度曲线和路径曲线,即可使用优化的方法求解得到最终的轨迹信息(s,s,s,l,l,l)。 本篇博客笔者主要介绍近…...

本地文件包含漏洞利用

目录 前期信息收集获取网站权限获取服务器权限纵向提权 前期信息收集 拿到目标的资产&#xff0c;先试一下IP能不能访问 探测一下目标的端口运行的是什么服务 nmap -sC -sV xx.xx9.95.185 -Pn获取网站权限 我们可以知道目标的80端口上运行着http服务&#xff0c;服务器是u…...

【docker】docker的常用命令

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;中间件 ⛺️稳中求进&#xff0c;晒太阳 常规命令 docker version #查看docker 版本信息docker info #显示docker 的系统信息&#xff0c;包括镜像和容器数量docker --help #查看所有的命…...

jmeter实战

jmeter学习 1&#xff0c;接口在定义时&#xff0c;post请求参数尽量放在body里面&#xff0c;get请求参数尽量放在parameters里面&#xff0c;否则会导致jmeter请求接口报错的问题(jmeter底层有较为严格的请求格式) 2&#xff0c;定义全局变量使用&#xff1a;Config Elemen…...

面试官常问问题

1、请你简单的自我介绍一下&#xff1f; 【Tips】① 口述内容不可与简历内容冲突&#xff1b;②阐述方式避免过度官方 且语速较快&#xff1b;③言简意赅&#xff0c;直击要害&#xff0c;抓重点突出项&#xff1b;④面试前应自己模拟练习几次&#xff0c;避免过度紧张导致的口…...

外包就干了2个月,技术退步明显....

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…...

面向对象 汇总(详细内容见Day12—16)

面向对象 汇总&#xff08;详细内容见Day12—16&#xff09; 文章目录 面向对象 汇总&#xff08;详细内容见Day12—16&#xff09;一、概念二、类三、对象四、成员属性/成员变量五、成员方法六、构造方法七、private - 私有化八、封装九、this - 本对象十、分包十一、static -…...

结构体联合体枚举和位段

文章目录 结构体结构体类型的声明特殊的声明 结构的自引用结构体变量的定义和初始化结构体内存对齐为什么要内存对齐结构体传参结构体实现位段&#xff08;位段的填充&可移植性&#xff09;位段位段的内存分配空间如何开辟位段的跨平台问题位段的应用 枚举枚举类型的定义枚…...

人类程序员真要失业?首位“AI软件工程师”亮相引爆科技圈

初创公司Cognition成立不到两个月&#xff0c;但已经拥有十名天才工程师。他们推出了一款名为Devin的人工智能&#xff08;AI&#xff09;助手&#xff0c;可以协助人类软件工程师完成各种开发任务。Devin与现有的其他AI编码者不同&#xff0c;它能够从头开始构建网站、自动部署…...

redis的过期策略以及内存淘汰机制

redis采用的是定期删除惰性删除策略。 为什么不用定时删除策略? 定时删除,用一个定时器来负责监视key,过期则自动删除。虽然内存及时释放&#xff0c;但是十分消耗CPU资源。在大并发请求下&#xff0c;CPU要 将时间应用在处理请求&#xff0c;而不是删除key,因此没有采用这一策…...

华为数通方向HCIP-DataCom H12-821题库(多选题:161-180)

第161题 以下关于IPv6优势的描述,正确的是哪些项? A、底层自身携带安全特性 B、加入了对自动配置地址的支持,能够无状态自动配置地址 C、路由表相比IPv4会更大,寻址更加精确 D、头部格式灵活,具有多个扩展头 【参考答案】ABD 【答案解析】 第162题 在OSPF视图下使用Filt…...

网络通信与网络协议

网络编程是指利用计算机网络实现程序之间通信的一种编程方式。在网络编程中&#xff0c;程序需要通过网络协议(如 TCP/IP)来进行通信&#xff0c;以实现不同计算机之间的数据传输和共享。在网络编程中&#xff0c;通常有三个基本要素 IP 地址:定位网络中某台计算机端口号port:定…...

【矩阵】240. 搜索二维矩阵 II【中等】

搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a;每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22…...

详解uniapp的生命周期

这篇文章主要介绍了 uniapp 的生命周期, 应用生命周期是指应用程序从启动到关闭的整个过程&#xff0c;包括应用程序的启动、前后台切换、退出等, 需要的朋友可以参考下 Uniapp 作为一款跨平台应用开发框架&#xff0c;具有丰富的生命周期&#xff0c;以下是 Uniapp 的生命周期…...

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:PluginComponent)

提供外部应用组件嵌入式显示功能&#xff0c;即外部应用提供的UI可在本应用内显示。 说明&#xff1a; 该组件从API Version 9开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。本组件为系统接口。 子组件 无 接口 PluginComponent(value:…...

mysql笔记:15. 事务和锁

文章目录 一、事务概述二、事务基本操作三、事务保存点四、事务的隔离级别1. READ UNCOMMITTED设置事务的隔离级别 2. READ COMMITTED3. REPEATABLE READ4. SERIALIZABLE 五、MySQL的锁InnoDB的锁类型1. InnoDB的行级锁2. InnoDB的表级锁 死锁 在开发过程中&#xff0c;我们经常…...

Learn OpenGL 15 面剔除

面剔除 尝试在脑子中想象一个3D立方体&#xff0c;数数你从任意方向最多能同时看到几个面。如果你的想象力不是过于丰富了&#xff0c;你应该能得出最大的面数是3。你可以从任意位置和任意方向看向这个球体&#xff0c;但你永远不能看到3个以上的面。所以我们为什么要浪费时间…...

EndeavourOs(arch系)安装sunpinyin输入法(ibus) + 迅雷(xunlei-bin)

输入法 yay -S ibus yay -S ibus-libpinyin yay -S ibus-sunpinyin yay -Q ibus ibus-libpinyin ibus-sunpinyin #验证 # 注销然后打开ibus config... # 在Input Method 添加Chinese->SunPinYin # 使用Ctrl Space, 默认Super Space, 请自行修改 # 再次注销&#xff0c;开…...

Spring Cache框架的介绍和使用

Spring Cache spring cache是一个框架&#xff0c;实现类基于注解的缓存功能&#xff0c;只需要简单的加一个注解&#xff0c;就能实现缓存功能&#xff0c;大大简化我们在业务中操作缓存的代码。 spring cache只是提供了一层抽象&#xff0c;底层可以切换不同的cache实现&am…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...