题意:
给出一棵符号树,要求加上括号输出正确的序列
思路:
这题一开始没想出来,不知道括号该怎么插入,实际上只要根节点和叶子节点不插入括号,其他的按中序正常插入即可。
#include<bits/stdc++.h>
using namespace std;struct node{string key;int left,right;
}tree[30];
int pre[30];void dfs(int root,int depth){if(root!=-1){if(depth!=0){if(!(tree[root].left==-1&&tree[root].right==-1))printf("(");}dfs(tree[root].left,depth+1);cout<<tree[root].key;dfs(tree[root].right,depth+1);if(depth!=0){if(!(tree[root].left==-1&&tree[root].right==-1))printf(")");}}
}int main(){int n,l,r;scanf("%d",&n);for(int i=1;i<=n;i++){cin>>tree[i].key>>l>>r;tree[i].left=l;tree[i].right=r;pre[l]=pre[r]=i;}int root;for(root=1;pre[root]!=0;root=pre[root]);dfs(root,0);return 0;
}