【PAT甲级】1130 Infix Expression (25分)（中序遍历输出加上括号后的运算字符串）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int vis[27];
 5 typedef struct node{
 6     int l,r;
 7     string s;
 8 }no;
 9 no tree[27];
10 int root;
11 vector<string>ans;
12 string dfs(int x){
13     if(x==-1)
14         return "";
15     if(tree[x].r!=-1){
16         tree[x].s=dfs(tree[x].l)+tree[x].s+dfs(tree[x].r);
17         if(x!=root)
18             tree[x].s="("+tree[x].s+")";
19     }
20     return tree[x].s;
21 }
22 int main(){
23     ios::sync_with_stdio(false);
24     cin.tie(NULL);
25     cout.tie(NULL);
26     int n;
27     cin>>n;
28     for(int i=1;i<=n;++i){
29         cin>>tree[i].s;
30         cin>>tree[i].l>>tree[i].r;
31         vis[tree[i].l]=1;
32         vis[tree[i].r]=1;
33     }
34     for(int i=1;i<=n;++i)
35         if(!vis[i])
36             root=i;
37     cout<<dfs(root);
38     return 0;
39 }