一、题目概述

依据给定语法树，输出后缀表达式

二、思路

对语法树后序遍历输出单元数据。
注意：单枝树按照先序NLR顺序输出数据

三、代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> lchild(21), rchild(21);
vector<string> data(21);
void postorder(int t)
{
	if( t != -1 )
	{
		bool tag = (lchild[t] * rchild[t] < 0);
		cout << "(";
		if( tag )
			cout << data[t];
		postorder(lchild[t]);
		postorder(rchild[t]);
		if( !tag )
			cout << data[t];
		cout << ")";
	}
}
int main()
{
	int N, root;
	cin >> N;
	vector<bool> isroot(N + 1, true);
	for( int i = 1; i <= N; ++i )
	{
		cin >> data[i] >> lchild[i] >> rchild[i];
		if( lchild[i] != -1 )
			isroot[lchild[i]] = false;
		if( rchild[i] != -1 )
			isroot[rchild[i]] = false;
	}
	for( root = 1; !isroot[root]; ++root );
	postorder(root);
}