<---
大佬们点个赞吧qwq
$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $
给定一个二叉表达式树,请你输出相应的后缀表达式,要求使用括号反映运算符的优先级。
输入格式
第一行包含整数 $N$,表示节点数量。节点编号 $1 \\sim N$。
接下来 $N$ 行,每行给出一个节点的信息(第 $i$ 行对应第 $i$ 个节点),格式为:
data left_child right_child
其中,data
是一个不超过 $10$ 个字符的字符串,left_child
和 right_child
分别是该节点的左右子节点的编号。
没有子节点(即 $NULL$),则用 $\-1$ 表示。
下面两图分别对应给出的两个样例。
输出格式
在一行中输出答案,表达式符号之间不得有空格。
数据范围
$1 \\le N \\le 20$
输入样例1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
输出样例1:
(((a)(b)+)((c)(-(d))*)*)
输入样例2:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
输出样例2:
(((a)(2.35)*)(-((str)(871)%))+)
思路
这道题在题目描述里图片都给出来了,那不是明摆着叫你建树吗……
1. 读取数据,建树
2. 找到根节点
3. 从根节点往下遍历,输出答案
坑点
这道题的坑点有一下几个:
1. -(a)
这种情况
2. 找根节点的时候注意空节点(但好像不注意也行啊,大雪莱不也过了吗)
C++代码
#include <iostream>
using namespace std;
const int N = 22;
int n;
string d[N]; // 存data
int l[N], r[N]; // 左右节点
bool st[N]; // 是否不是根节点
string suffix(int x)
{
if (~l[x] && ~r[x]) return '(' + suffix(l[x]) + suffix(r[x]) + d[x] + ')'; // 左右儿子都非空(如 ((a)(b)+),父亲为'+')
if (~r[x]) return '(' + d[x] + suffix(r[x]) + ')'; // 右儿子非空(那么左儿子就是空的,因为上面已经排除掉了,如 (-(a)),父亲为'-')
return '(' + d[x] + ')'; // 左右儿子都为空(如 (a),父亲为'a')
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) // 读入数据
{
cin >> d[i] >> l[i] >> r[i]; // 记录数据
if (~l[i]) st[l[i]] = true; // 如果某个节点已经是其他节点的儿子了,则它肯定不是根节点(注意空节点的情况)
if (~r[i]) st[r[i]] = true; // 同理
}
int root; // 根节点
for (int i = 1; i <= n; i ++ ) // 遍历所有节点
if (!st[i]) // 它是根节点
{
root = i; // 找到了
break; // 退出循环
}
cout << suffix(root); // 输出答案
return 0; // 圆满结束
}
我现在都懒得求赞了QWQ