【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之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
