题目描述

输入一棵普通有序树，输出该树的前序和后序次序。

输入

顶点个数n(1<=n<=200)
以下含n行，其中第i行（1<=i<=n)的元素依此为结点的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。

输出

输出两行，分别为普通有序树的前序和后序次序

输入数据 1

4
A 2 3 4 0
B 0
C 0
D 0

输出数据 1

ABCD
DCBA

---

代码

#include <bits/stdc++.h>
using namespace std;
int n, x;
struct node{
	char c;
	int cnt, k[1000], f;
}a[1000];
int find(int x){
	if(x != a[x].f) find(a[x].f);
	return x;
}
void xfs(int x){
	if(!x) return ;
	cout << a[x].c;
	for(int i = 1; i <= a[x].cnt; i++)
		xfs(a[x].k[i]);
}
void hfs(int x){
	if(!x) return ;
	for(int i = a[x].cnt; i >= 1; i--)
		hfs(a[x].k[i]);
	cout << a[x].c;
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) a[i].f = i;
	for(int i = 1; i <= n; i++){
		cin >> a[i].c >> x;
		while(x){
			a[x].f = i;
			a[i].k[++a[i].cnt] = x;
			cin >> x;
		}
	}
	int root = find(1);
	xfs(root);
	cout << endl;
	hfs(root);
	return 0;
}