后缀表达式
题目描述
给定一个二叉表达式树,请你输出相应的后缀表达式,要求使用括号反映运算符的优先级。
输入格式
第一行包含整数 $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)%))+)
正解:树的后序遍历
思路
我们观察样例的两幅图发现有三种情况:
-
当前节点没有任何的子节点,直接输出
(这个节点的 data)
-
当前节点只有一个子节点,输出
(这个节点的 data,唯一的子树)
(不包含,
号) -
当前节点有两个子节点,输出
(左子树,右子树,这个节点的 data)
(不包含,
号)
第一种情况的处理很简单,这里不再讨论。
第二种情况就先输出这个节点的 data
,再 dfs
它的唯一子树,相对来说也比较简单。
我们来观察第三种情况中树的遍历顺序,因为这道题要输出后缀表达式,所以应该 按照 “左 - 右 - 根” 的顺序(即先访问它的左子树,再访问它的右子树,最后输出当前节点的 data
) 来访问这棵树,这正好是树的后序遍历!
具体实现
新建一些数组,l
数组来存当前节点的左子节点,r
数组来存当前节点的右子节点,a
数组来存当前节点的 data
,cnt
数组来存当前节点有多少个子节点(不为 $NULL$),vis
数组来存当前节点是否为某个节点的子节点。
输入并按照上述方法处理完后,我们从 $1 \sim n$ 枚举 $root$,如果 $vis[root] == 0$,那么就表示 $root$ 是整棵树的根节点,直接 dfs (root)
。
我们在 dfs
时,先判断如果 cnt[x] == 0
,直接输出 (a[x])
并返回即可。否则如果 cnt[x] == 1
,输出 (a[x]
,dfs
它的唯一子树,再输出 )
并直接返回。否则先输出 (
,再分别 dfs
它的左子树和右子树,最后输出 a[x])
并返回。
dfs
函数写法(仅供参考)
void dfs (int x)
{
if (!cnt[x])
{
cout << "(" << a[x] << ")";
return ;
}
if (cnt[x] == 1)
{
cout << "(" << a[x], dfs (~l[x] ? l[x] : r[x]), cout << ")";
return ;
}
cout << "(", dfs (l[x]), dfs (r[x]), cout << a[x] << ")";
return ;
}
AC Code
#include <iostream>
#define N 25
#define add() a[i]=s,l[i]=x,r[i]=y,cnt[i]=(bool)~x+(bool)~y,vis[x]=~x,vis[y]=~y
using namespace std;
int n, x, y, root, t, null, l[N], r[N], cnt[N];
bool vis[N];
string s, a[N];
void dfs (int x)
{
if (!cnt[x])
{
cout << "(" << a[x] << ")";
return ;
}
if (cnt[x] == 1)
{
cout << "(" << a[x], dfs (~l[x] ? l[x] : r[x]), cout << ")";
return ;
}
cout << "(", dfs (l[x]), dfs (r[x]), cout << a[x] << ")";
return ;
}
int main ()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> s >> x >> y, add ();
}
for (root = 1; vis[root]; root ++);
dfs (root);
return 0;
}