PAT 甲级 刷题日记|A 1130 Infix Express

题目

见官网

思路

这道题建树，遍历平平无奇。只是有两点需要注意：

• 根节点的位置需要自己寻找：未出现在别人孩子位置的节点即为根节点
• 在输出时，括号需要稍作处理。通过观察可以发现，中序遍历输出时，非根非叶节点需要输出括号。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 23;
struct node {
    string data;
    int lchild, rchild;
}Node[maxn];
int n;
int flag[maxn];

void inorder(int root) {
    if (root == -1) return;
    if (flag[root] == 1 && ( Node[root].lchild != -1 || Node[root].rchild != -1)) cout<<"(";
    inorder(Node[root].lchild);
    cout<<Node[root].data;
    inorder(Node[root].rchild);
    if (flag[root] == 1 && (Node[root].lchild != -1 || Node[root].rchild != -1)) cout<<")";
}

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>Node[i].data>>Node[i].lchild>>Node[i].rchild;
        if (Node[i].lchild != -1) flag[Node[i].lchild] = 1;
        if (Node[i].rchild != -1) flag[Node[i].rchild] = 1;
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (flag[i] != 1) {
            root = i;
            break;
        }
    }
    inorder(root);
}