1130 Infix Expression（25 分）

DFS

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 50;
struct Node {
    string data;
    int lchild, rchild;
}node[maxn];
bool isroot[maxn];
int root = 0;
string DFS(int index)
{
    if (index == -1)return "";
    else
    {
        if (node[index].rchild != -1)
        {
            node[index].data = DFS(node[index].lchild) + node[index].data + DFS(node[index].rchild);
            if (index != root)node[index].data = "(" + node[index].data + ")";
        }
        return node[index].data;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    for (int i = 1; i <= n; i++)
    {
        cin >> node[i].data >> node[i].lchild >> node[i].rchild;
        if (node[i].lchild != -1)isroot[node[i].lchild] = true;
        if (node[i].rchild != -1)isroot[node[i].rchild] = true;
    }

    for (int i = 1; i <= n; i++)
    {
        if (isroot[i] == false)
        {
            root = i;
            break;
        }
    }
    cout<<DFS(root);

    return 0;
}