【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伪指令可以将任…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
