当前位置: 代码迷 >> 综合 >> PAT1130 Infix Expression(树的递归)
  详细解决方案

PAT1130 Infix Expression(树的递归)

热度:86   发布时间:2024-01-16 13:16:11.0

题意:

给出一棵符号树,要求加上括号输出正确的序列

思路:

这题一开始没想出来,不知道括号该怎么插入,实际上只要根节点和叶子节点不插入括号,其他的按中序正常插入即可。

#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;
}

 

  相关解决方案