[保研/考研机试] KY212 二叉树遍历 华中科技大学复试上机题 C++实现

题目链接:

二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/437195121692587727256

描述

二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入描述:

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

输出描述:

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

示例1

输入:

ABC
BAC
FDXEAG
XDEFAG

输出:

BCA
XEDGAF

思路:

先来一个例子:

先序遍历序列为:FDXEAG

中序遍历序列为:XDEFAG

要根据先序序列和中序序列确定这个二叉树,通用的步骤为:

1.根据先序序列的第一位确定这棵树的根;

2.在中序序列中找到根的所在的位置,根的左边就是该树的左子树的节点,根的右边就是该树的右子树的节点;

3.根据树的左子树节点和右子树节点在先序序列中分别找到对应的子串;

4.对3中找到的两个子串分别重复1 2 3步,左子树节点用于构建左子树,右子树节点用于构建右子树,直到所有的节点都用于构建这棵树。

示例:

根据以上的案例走一遍:

1.由先序遍历序列为:FDXEAG可知,树的根节点为F;

2.在中序遍历序列XDEFAG找到F的索引为3,左边XDE就是该树的左子树的节点,右边AG就是该树的右子树的节点;

3.根据树的左子树节点XDE和右子树节点AG在先序序列中分别找到对应的子串,分别为:DXE和AG;

4.对DXE和AG分别重复步骤1 2 3,DXE用于构建左子树,AG用于构建右子树,直到所有的节点都用于构建树。

每执行完第一轮步骤1 2 3,所用的根节点已经用于构建树了,后续就不用再考虑了。例如,执行完第一轮步骤1 2 3,根节点F已经用过了,后续就不用再考虑了。

分析:

相信思路都很明确,步骤大概也明白了,接下来代码实现中一个非常注重细节的地方就是递归构建左子树和右子树的部分,再详细说就是在递归调用构建树的函数中,我们要传入的两个参数应该怎么确定。

本次主要介绍利用先序遍历序列和中序遍历构建一个二叉树并输出后序遍历的方法,我们在递归调用构建树的函数中,我们要传入的两个参数当然就是子树的先序遍历序列和中序遍历序列。创建左子树时就传入左子树的先序遍历序列和中序遍历序列,创建右子树时就传入右子树的先序遍历序列和中序遍历序列。

以下根据以上案例详细分析:对于:

索         引:012345
先序遍历序列为:FDXEAG中序遍历序列为:XDEFAG

将以上两个遍历序列分别命名为字符串s1,s2,即s1 = "FDXEAG", s2 = "XDEFAG"。根据s1可知树的根为F,在s2中寻找到F的索引(定义为pos)为3。根据s2可得左子树包括的字符有:XDE(由s2.substr(0, pos)获得),右子树包括的字符有:AG(由s2.substr(pos+1)获得),在s1中对应的字符串分别为:DXE(由s1.substr(1, pos)获得)和AG(由s1.substr(pos+1)获得)。根据以上获得的四个参数,可以递归创建左子树和右子树。

源代码:

//根据先序遍历和中序遍历确定一个二叉树
// 二叉树节点结构定义
struct TreeNode {char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
};// 根据先序遍历和中序遍历构建二叉树
TreeNode* Build(string str1, string str2) {if (str1.size() == 0) {return NULL;}// 取先序遍历的第一个字符作为根节点char c = str1[0];// 在中序遍历中找到根节点的位置int pos = str2.find(c);// 创建根节点TreeNode* root = new TreeNode(c);递归构建左子树root->leftChild = Build(str1.substr(1, pos), str2.substr(0, pos));递归构建右子树root->rightChild = Build(str1.substr(pos + 1), str2.substr(pos + 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;while (getline(cin, s1)) {getline(cin, s2);TreeNode* root = Build(s1, s2);postOrder(root);cout << endl;}return 0;
}

示例运行结果:

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

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

相关文章

网络丢包故障如何定位?如何解决?

引言 本期分享一个比较常见的网络问题--丢包。例如我们去ping一个网站&#xff0c;如果能ping通&#xff0c;且网站返回信息全面&#xff0c;则说明与网站服务器的通信是畅通的&#xff0c;如果ping不通&#xff0c;或者网站返回的信息不全等&#xff0c;则很可能是数据被丢包了…

pyqt5 多线程QThread自学记录

pyqt5多线程QThread自学记录 在编写qt的时候不加入多线程&#xff0c;运行程序往往会导致主进程卡死&#xff0c;比如执行下载某视频或者其他执行比较耗时的程序&#xff0c;泛滥了博客&#xff0c;就是没有理解怎么进行槽函数的关联和传递的 经过长时间的攻克&#xff0c;终于…

TCP编程流程(补充)

目录 1、listen&#xff1a; 2、listen、tcp三次握手 3、 发送缓冲区和接收缓冲区&#xff1a; 4、tcp编程启用多线程 1、listen&#xff1a; 执行listen会创建一个监听队列 listen(sockfd,5) 2、listen、tcp三次握手 三次握手 3、 发送缓冲区和接收缓冲区&#xff1a;…

【C++入门到精通】C++入门 —— 模版(template)

阅读导航 前言一、模版的概念二、函数模版1. 函数模板概念2. 函数模板定义格式3. 函数模板的原理4. 函数模版的实例化&#x1f6a9;隐式实例化&#x1f6a9;显式实例化 5. 函数模板的匹配原则 三、类模板1. 类模板的定义格式2. 类模板的实例化 四、非类型模板参数1. 概念2. 定义…

攻击LNMP架构Web应用

环境配置(centos7) 1.php56 php56-fpm //配置epel yum install epel-release rpm -ivh http://rpms.famillecollet.com/enterprise/remi-release-7.rpm//安装php56&#xff0c;php56-fpm及其依赖 yum --enablereporemi install php56-php yum --enablereporemi install php…

vscode里配置C#环境并运行.cs文件

vscode是一款跨平台、轻量级、开源的IDE, 支持C、C、Java、C#、R、Python、Go、Nodejs等多种语言的开发和调试。下面介绍在vscode里配置C#环境。这里以配置.Net SDK v5.0&#xff0c;语言版本为C#9.0&#xff0c;对应的开发平台为VS2019&#xff0c;作为案例说明。 1、下载vsc…

【LeetCode-经典面试150题-day9]

目录 36.有效的数独 54.螺旋矩阵 48.旋转图像 73.矩阵置零 36.有效的数独 题意&#xff1a; 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1…

25岁无经验入行软件测试的感悟,写给还在迷茫中的你

转行软件测试两年了&#xff0c;这两年来&#xff0c;从刚开始对测试认识的朦朦胧胧&#xff0c;现在思路也逐渐清晰了&#xff0c;也明确了自己的发展方向。虽然对那些测试理论和测试工具以及测试技术有了一些加强&#xff0c;但是自我感觉还是不够深入。 我一直希望能真正融…

《网络是怎样连接的》(四)

本文主要取材于 《网络是怎样连接的》 第四章。 目录 4.1 互联网的基本结构 4.2光纤接入网&#xff08;FTTH&#xff09; 4.3 接入网中使用的PPP和隧道 4.4 网络运营商的内部 4.5 跨越运营商的网络包 简述&#xff1a;本文主要内容是解释 网络包是如何通过互联网接入路由…

【0823作业】C++:实现类嵌套,以及其构造函数、析构函数和拷贝构造函数

要求&#xff1a; 设计一个Per类。类中包含私有成员&#xff1a;姓名、年龄、指针成员身高、体重&#xff1b; 再设计一个Stu类&#xff0c;类中包含私有成员&#xff1a;成绩、Per类对象 p1&#xff1b; 设计这两个类的构造函数、析构函数和拷贝构造函数。 #include <iostr…

【广州华锐视点】AR配电所巡检系统:可视化巡检利器

随着科技的发展&#xff0c;人工智能、大数据等技术逐渐应用于各个领域&#xff0c;为人们的生活带来便利。在电力行业&#xff0c;AR(增强现实)技术的应用也日益广泛。AR配电所巡检系统作为一种新型的巡检方式&#xff0c;可以实现多种功能&#xff0c;提高巡检效率&#xff0…

如何在Windows、Mac和Linux操作系统上安装Protocol Buffers(protobuf)编译器

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

Android类加载机制

要说Android的类加载机制 &#xff0c;就离不开 类加载器ClassLoader&#xff0c;它是一个抽象接口 下面这个图还是比较好表达了类加载流程&#xff0c;但如果不看我红色画的线&#xff0c;就会感觉有点乱&#xff0c;需要注意是采用的是双亲委派模式&#xff0c;class加载要先…

测试驱动开发(TDD)

测试驱动开发&#xff08;TDD&#xff09; 本篇文章简单叙述一下什么是测试驱动开发&#xff0c;以及怎么进行测试驱动开发&#xff01; TDD &#xff08;Test Driven Development&#xff09;&#xff1a;&#xff08;源于极限编程&#xff08;XP&#xff09;&#xff09;在不…

9.Sentinel哨兵

1.Sentinel Sentinel&#xff08;哨兵&#xff09;是由阿里开源的一款流量控制和熔断降级框架&#xff0c;用于保护分布式系统中的应用免受流量涌入、超载和故障的影响。它可以作为微服务架构中的一部分&#xff0c;用于保护服务不被异常流量冲垮&#xff0c;从而提高系统的稳定…

JavaSE 数组

定义&#xff1a; int []arr; int arr[]; 初始化 // 完整格式 int arr[] new int[]{1, 2, 3}; // 简单格式 int arr[] {1, 2, 3}; 数组的元素访问、遍历 按照下标访问即可。数组的长度函数为 arr.length()。idea快速生成遍历的方法&#xff1a;数组名.fori 静态初始化 &a…

element时间选择器el-date-picter使用disabledDate指定禁用的日期

需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…

5G+AI数字化智能工厂建设解决方案PPT

导读&#xff1a;原文《5GAI数字化智能工厂建设解决方案》&#xff08;获取来源见文尾&#xff09;&#xff0c;本文精选其中精华及架构部分&#xff0c;逻辑清晰、内容完整&#xff0c;为快速形成售前方案提供参考。数字化智能工厂定义 智能基础架构协同框架 - 端、边、云、网…

微信小程序手机号验证开发遇到问题

公司小程序项目中快速登录需要实现微信用户授权手机登录、注册功能。结果遇到了 invalid code hint: [zHkDmt0sf-MBjga] rid: 64e3259f-1091b953-7e10f1da 目录 服务端文档 文档描述 返回信息 服务端代码 遇到问题 排查问题 1.服务端用错了appid serect 2.小程序端用错…

C++(Qt)软件调试---gdb调试入门用法(12)

gdb调试—入门用法&#xff08;1&#xff09; 文章目录 gdb调试---入门用法&#xff08;1&#xff09;1、前言1.1 什么是GDB1.2 为什么要学习GDB1.3 主要内容1.4 GDB资料 2、C/C开发调试环境准备3、gdb启动调试1.1 启动调试并传入参数1.2 附加到进程1.3 过程执行1.4 退出调试 4…