对于一棵表达式树,中序遍历得到中缀表达式,前序遍历得到前缀表达式,后序遍历得到后缀表达式
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
string d[N];
int l[N], r[N], n;
bool st[N];//有父节点true
void dfs(int root){
cout<<"(";
if(l[root] != -1 && r[root] != -1){
dfs(l[root]);
dfs(r[root]);
cout<<d[root];
}else if(l[root] == -1 && r[root] == -1){
cout<<d[root];
}else if(l[root] == -1 && r[root] != -1){//当前节点是一个负号(非减)
cout<<d[root];//先输出负号
dfs(r[root]);
}
cout<<")";
}
int main(){
cin>>n;
for(int i=1; i<=n; i++){
cin>>d[i]>>l[i]>>r[i];
//判断l[i]和r[i]是否有父节点
if(l[i] != -1) st[l[i]] = true;
if(r[i] != -1) st[r[i]] = true;
}
int root;
for(int i=1; i<=n; i++)
if(!st[i])
root = i;
dfs(root);
return 0;
}