1130 Infix Expression （中缀表达式、2017年408大题，中序遍历解决）

时间：2020-03-17 15:39:14 收藏：0 阅读：61

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805347921805312

那天模拟考试做这道题时，直接把我心态搞崩了。如今再做这道题，感触颇深啊~

借助中序遍历，除了根结点和叶子结点，遍历到其它结点时，在遍历其左子树之前加上左括号，在遍历其右子树之后加上右括号。

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 
 5 struct Node {
 6     string data;
 7     int lchild,rchild;
 8 };
 9 vector<Node> tree;
10 vector<bool> visited;
11 
12 void inorder(int root,int depth) {
13     if(root == -1) return; //空结点直接返回 
14     else if(tree[root].lchild == -1 && tree[root].rchild == -1) //叶子结点 
15         printf("%s",tree[root].data.c_str());
16     else {
17         if(depth > 1) printf("(");
18         inorder(tree[root].lchild,depth+1);
19         printf("%s",tree[root].data.c_str());
20         inorder(tree[root].rchild,depth+1);
21         if(depth > 1) printf(")");
22     }
23 }
24 
25 int main() {
26     int n,l,r;
27     scanf("%d",&n);
28     visited.resize(n+1);
29     tree.resize(n+1);
30     string data;
31     for(int i = 1; i <= n; ++i) {
32         cin>>data>>l>>r;
33         tree[i].data = data;
34         tree[i].lchild = l;
35         tree[i].rchild = r;
36         if(l > 0) visited[l] = true;
37         if(r > 0) visited[r] = true;
38     }
39     int root;
40     for(int i = 1; i <= n; ++i)
41         if(visited[i] == false) {
42             root = i;
43             break;
44         }
45     inorder(root,1);
46     return 0;
47 }

技术分享图片

原文：https://www.cnblogs.com/keep23456/p/12510720.html