4274. 后缀表达式-二叉表达式树

原题链接

• 二叉表达式树的后序遍历就是后缀表达式
• 特例：怎么区分表达式中的正号与加号，负号和减号呢？
  答：如果某个节点是“+”或“-”号，并且其左子树为空时，则该符号为正（负）号，而不是加减号，那么对该节点进行先序遍历而不是后序遍历

#include 
using namespace std;

const int N = 25;
int t[N][2], vis[N];
int n;
string v[N];

void traverse(int node)
{
    if (node == -1)
        return;
    if ((v[node] == "-" || v[node] == "+") && t[node][0] == -1)
    {
        cout << "(" << v[node];
        traverse(t[node][1]);
        cout << ")";
    }
    else
    {
        cout << "(";
        traverse(t[node][0]);
        traverse(t[node][1]);
        cout << v[node];
        cout << ")";
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> t[i][0] >> t[i][1];
        if (t[i][0] != -1)
            vis[t[i][0]] = 1;
        if (t[i][1] != -1)
            vis[t[i][1]] = 1;
    }

    int p;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            p = i;
            break;
        }
    }
    traverse(p);
    return 0;
}