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

【2017年数据结构真题】

请设计一个算法,将给定的表达式树(二叉树)转换成等价的中缀表达式(通过括号反映次序),并输出。例如,当下列两棵表达式树作为算法的输入时:

image.png

输出的等价中缀表达式分别为(a+b)(a(-d)) 和 (a * b)+(-(c-d))

二叉树结点定义如下:

typedef struct node
{char date[10]; //存储操作数或者操作符struct node *left, *right;
} BTree;

要求:

(1) 给出算法的基本思想

(2) 根据设计思想,采用c/c++语言描述算法,关键之处给出注释

算法思想:基于二叉树的中缀遍历,添加适当括号,显然,表达式的最外层(对于根节点)及操作数

(对应叶节点)不需要添加括号(这句是答案说的,其实不太懂)


void B2E(BTree *root)
{B2E(root, 1);
}
void B2E(BTree *root, int deep)
{if (root == NULL)printf("NULL");else if (root->left == NULL && root->right == NULL) //叶节点printf("%s", root->data);                       //输出操作数else{if (deep > 1)printf("(");B2E(root->left, deep + 1);printf("%s", root->data); //输出操作符B2E(root->right, deep + 1);if (deep > 1)printf(")");}
}

解决方法:

(1)算法的基本设计思想

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基

于二叉树的中序遍历策略得到所需的表达式。(3 分)

表达式树中分支结点所对应的子表达式的计算次序,由该分支结点所

处的位置决定。为得到正确的中缀表达式,需要在生成遍历序列的同

时,在适当位置增加必要的括号。显然,表达式的最外层(对应根结点)

及操作数(对应叶结点)不需要添加括号。(2 分)

(2)算法实现(10 分)

将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和

叶结点外,遍历到其他结点时在遍历其左子树之前加上左括号,在遍

历完右子树后加上右括号。

相关文章:

【2017年数据结构真题】

请设计一个算法,将给定的表达式树(二叉树)转换成等价的中缀表达式(通过括号反映次序),并输出。例如,当下列两棵表达式树作为算法的输入时: 输出的等价中缀表达式分别为(ab)(a(-d)) 和…...

神辅助 Cursor 编辑器,加入 GPT-4 让编码更轻松!

分类 互联网 在 ChatGPT 问世之前,我们的编码方式很多时候都是面向搜索引擎编码,需要不断地进行搜索,然后复制粘贴,俗称复制粘贴工程师。 但是,随着ChatGPT的出现,这一切将彻底改变。 ChatGPT 是一种基于…...

解决Qt5.13.0无MySQL驱动问题

一、前言 由于Qt5.12.3是最后提供mysql数据库插件的版本,往后的版本需要自行编译对应的mysql数据库插件,官方安装包不再提供。使用高版本的Qt就需要自行编译mysql驱动。 若没有编译在QT中调用Qsqldatabase库连接mysql时,提示出现如下问题&a…...

YOLOv8改进 | 如何在网络结构中添加注意力机制、C2f、卷积、Neck、检测头

一、本文介绍 本篇文章的内容是在大家得到一个改进版本的C2f一个新的注意力机制、或者一个新的卷积模块、或者是检测头的时候如何替换我们YOLOv8模型中的原有的模块,从而用你的模块去进行训练模型或者检测。因为最近开了一个专栏里面涉及到挺多改进的地方&#xff…...

记录一个困难

Mysql加插件 create table tb_xuesheng1 as select * from tb_xuesheng; 会报如下错误 SQL 错误 [3185] [HY000]: Cant find master key from keyring, please check in the server log if a keyring is loaded and initialized successfully.当我去搜寻答案网上都说缺少插件…...

Linux 进程管理 实时调度类及SMP和NUMA

文章目录 一、 实时调度类分析1.1 实时调度实体sched_rt_entity数据结构1.2 实时调度类rt_sched_class数据结构1.3 实时调度类功能函数 二、SMP和NUMA2.1 SMP(多对称处理器结构,UMA)2.2 NUMA(非一致内存访问结构)2.3 C…...

线性表--链表-1

文章目录 主要内容一.链表练习题1.设计一个递归算法,删除不带头结点的单链表 L 中所有值为 X 的结点代码如下(示例): 2.设 L为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值代码如下(示例): …...

WPF小知识

在编写WPF程序遇到一些小问题&#xff0c;所以记录起来&#xff0c;查其他方便。 Label自动换行 网上搜的都不能自动换行&#xff0c;发现使用Run 就可以。在脚本中直接调用labTip.Text进行赋值就可以了。 <Label Foreground"#FF9E9E9E" FontSize"16"…...

坐标系下的运动旋量转换

坐标系下的运动旋量转换 文章目录 坐标系下的运动旋量转换前言一、运动旋量物体运动旋量空间运动旋量 二、伴随变换矩阵三、坐标系下运动旋量的转换四、力旋量五、总结参考资料 前言 对于刚体而言&#xff0c;其角速度可以写为 ω ^ θ ˙ \hat {\omega} \dot \theta ω^θ˙&…...

Android Termux安装MySQL,通过内网穿透实现公网远程访问

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f516;系列专栏&#xff1a; C语言、Linux、Cpolar ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前…...

Python in Visual Studio Code 2023年11月发布

排版&#xff1a;Alan Wang 我们很高兴地宣布 Visual Studio Code 的 Python 和 Jupyter 扩展将于 2023 年 11 月发布&#xff01; 此版本包括以下公告&#xff1a; 改进了使用 Shift Enter 在终端中运行当前行弃用内置 linting 和格式设置功能对 Python linting 扩展的改进重…...

算法通关村——数字中的统计、溢出、进制转换处理模板

数字与数学基础问题 1、数字统计 1.1、符号统计 LeetCode1822. 给定一个数组&#xff0c;求所有元素的乘积的符号&#xff0c;如果最终答案是负的返回-1&#xff0c;如果最终答案是正的返回1&#xff0c;如果答案是0返回0. 这题其实只用看数组中0和负数的个数就好了&#x…...

ESP01S通过心知天气获取天气和时间信息

ESP01S通过心知天气获取天气和时间信息 设置STA模式 ATCWMODE1 连接wifi ATCWJAP"wifi名称","wifi密码"3.设置时间地域 ATCIPSNTPCFG1,8获取时间 ATCIPSNTPTIME?返回&#xff1a; CIPSNTPTIME:Fri Nov 17 17:09:22 2023 OK连接心知服务器 ATCIPSTAR…...

docker容器内core dumped却找不到core文件

1. 检查ulimit&#xff0c; 使用命令&#xff1a; ulimit -a rootb7c19f6da1e3:/usr# ulimit -a core file size (blocks, -c) unlimited data seg size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks…...

ubuntu提高 github下载速度

Github一般用于Git的远程仓库&#xff0c;由于服务器位于国外&#xff0c;国内访问速度比较慢&#xff0c;为了提高访问速度&#xff0c;决定绕过DNS域名解析。 获取Github的IP地址 按下ctrl&#xff0b;alt&#xff0b;T打开命令终端&#xff0c;输入&#xff1a; nslookup gi…...

Node.js之path路径模块

让我为大家介绍一下path路径模块吧&#xff01; 什么是path路径模块&#xff1f; path 模块是 Node.s 官方提供的、用来处理路径的模块。它提供了一系列的方法和属性&#xff0c;用来满足用户对路径的处理需求。 介绍三个关于path模块的方法&#xff1a; path.join() 方法&…...

TCP与UDP协议

TCP与UDP协议 1、TCP协议&#xff1a; 1、TCP特性&#xff1a; TCP 提供一种面向连接的、可靠的字节流服务。在一个 TCP 连接中&#xff0c;仅有两方进行彼此通信。广播和多播不能用于 TCP。TCP 使用校验和&#xff0c;确认和重传机制来保证可靠传输。TCP 给数据分节进行排序…...

“ /^A-Z:\\{1,2}^/:\*\?<>\|+\.(jpg|gif|png|bmp)$/i ”这个正则表达式的理解

这个正则表达式可以分解为以下几个部分&#xff1a; ^&#xff1a;这是一个开始符号&#xff0c;表示匹配必须从字符串的开始部分开始。/&#xff1a;这是一个斜杠符号&#xff0c;通常在正则表达式中用来表示特殊字符的转义。A-Z:&#xff1a;这部分表示匹配一个大写字母后跟…...

批量下载Sentinel数据脚本2023

批量下载Sentinel数据脚本2023 那些最好的程序员不是为了得到更高的薪水或者得到公众的仰慕而编程&#xff0c;他们只是觉得这是一件有趣的事情&#xff01; 批量下载Sentinel数据脚本2023 批量下载Sentinel数据脚本2023&#x1f33f;前言&#x1f33f;脚本地址&#x1f4e7;Su…...

lv11 嵌入式开发 ARM指令集中(伪操作与混合编程) 7

目录 1 伪指令 2 伪操作 3 C和汇编的混合编程 4 ATPCS协议 1 伪指令 本身不是指令&#xff0c;编译器可以将其替换成若干条等效指令 空指令NOP 指令LDR R1, [R2] 将R2指向的内存空间中的数据读取到R1寄存器 伪指令LDR R1, 0x12345678 R1 0x12345678 LDR伪指令可以将任…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...