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

输出的等价中缀表达式分别为(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模型中的原有的模块,从而用你的模块去进行训练模型或者检测。因为最近开了一个专栏里面涉及到挺多改进的地方ÿ…...
记录一个困难
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程序遇到一些小问题,所以记录起来,查其他方便。 Label自动换行 网上搜的都不能自动换行,发现使用Run 就可以。在脚本中直接调用labTip.Text进行赋值就可以了。 <Label Foreground"#FF9E9E9E" FontSize"16"…...
坐标系下的运动旋量转换
坐标系下的运动旋量转换 文章目录 坐标系下的运动旋量转换前言一、运动旋量物体运动旋量空间运动旋量 二、伴随变换矩阵三、坐标系下运动旋量的转换四、力旋量五、总结参考资料 前言 对于刚体而言,其角速度可以写为 ω ^ θ ˙ \hat {\omega} \dot \theta ω^θ˙&…...
Android Termux安装MySQL,通过内网穿透实现公网远程访问
🔥博客主页: 小羊失眠啦. 🔖系列专栏: C语言、Linux、Cpolar ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前…...
Python in Visual Studio Code 2023年11月发布
排版:Alan Wang 我们很高兴地宣布 Visual Studio Code 的 Python 和 Jupyter 扩展将于 2023 年 11 月发布! 此版本包括以下公告: 改进了使用 Shift Enter 在终端中运行当前行弃用内置 linting 和格式设置功能对 Python linting 扩展的改进重…...
算法通关村——数字中的统计、溢出、进制转换处理模板
数字与数学基础问题 1、数字统计 1.1、符号统计 LeetCode1822. 给定一个数组,求所有元素的乘积的符号,如果最终答案是负的返回-1,如果最终答案是正的返回1,如果答案是0返回0. 这题其实只用看数组中0和负数的个数就好了&#x…...
ESP01S通过心知天气获取天气和时间信息
ESP01S通过心知天气获取天气和时间信息 设置STA模式 ATCWMODE1 连接wifi ATCWJAP"wifi名称","wifi密码"3.设置时间地域 ATCIPSNTPCFG1,8获取时间 ATCIPSNTPTIME?返回: CIPSNTPTIME:Fri Nov 17 17:09:22 2023 OK连接心知服务器 ATCIPSTAR…...
docker容器内core dumped却找不到core文件
1. 检查ulimit, 使用命令: 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的远程仓库,由于服务器位于国外,国内访问速度比较慢,为了提高访问速度,决定绕过DNS域名解析。 获取Github的IP地址 按下ctrl+alt+T打开命令终端,输入: nslookup gi…...
Node.js之path路径模块
让我为大家介绍一下path路径模块吧! 什么是path路径模块? path 模块是 Node.s 官方提供的、用来处理路径的模块。它提供了一系列的方法和属性,用来满足用户对路径的处理需求。 介绍三个关于path模块的方法: path.join() 方法&…...
TCP与UDP协议
TCP与UDP协议 1、TCP协议: 1、TCP特性: TCP 提供一种面向连接的、可靠的字节流服务。在一个 TCP 连接中,仅有两方进行彼此通信。广播和多播不能用于 TCP。TCP 使用校验和,确认和重传机制来保证可靠传输。TCP 给数据分节进行排序…...
“ /^A-Z:\\{1,2}^/:\*\?<>\|+\.(jpg|gif|png|bmp)$/i ”这个正则表达式的理解
这个正则表达式可以分解为以下几个部分: ^:这是一个开始符号,表示匹配必须从字符串的开始部分开始。/:这是一个斜杠符号,通常在正则表达式中用来表示特殊字符的转义。A-Z::这部分表示匹配一个大写字母后跟…...
批量下载Sentinel数据脚本2023
批量下载Sentinel数据脚本2023 那些最好的程序员不是为了得到更高的薪水或者得到公众的仰慕而编程,他们只是觉得这是一件有趣的事情! 批量下载Sentinel数据脚本2023 批量下载Sentinel数据脚本2023🌿前言🌿脚本地址📧Su…...
lv11 嵌入式开发 ARM指令集中(伪操作与混合编程) 7
目录 1 伪指令 2 伪操作 3 C和汇编的混合编程 4 ATPCS协议 1 伪指令 本身不是指令,编译器可以将其替换成若干条等效指令 空指令NOP 指令LDR R1, [R2] 将R2指向的内存空间中的数据读取到R1寄存器 伪指令LDR R1, 0x12345678 R1 0x12345678 LDR伪指令可以将任…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
