AOJ ALDS1_7_C 木の巡回

AOJ ALDS1_7_C 木の巡回

問題概要

リンク参照

問題リンク

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C

考察

• ただただ実装するだけではあるけど今まで書いたことがなかったので勉強になった．
• 出力と再帰で潜るタイミングを変えれば良い

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<complex>
#include<list>
#include<cstdio>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)


using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;




const int INF = 1e9 + 7;


/******************************************************************************************/


vector<int> G[30];
int in[30];

void preParse(int now) {

	if (now == -1) {
		return;
	}
	
	cout << " " << now;
	
	preParse(G[now][0]);
	preParse(G[now][1]);
}


void inParse(int now) {

	if (now == -1) {
		return;
	}

	inParse(G[now][0]);

	cout << " " << now;

	inParse(G[now][1]);
}


void postParse(int now) {

	if (now == -1) {
		return;
	}

	postParse(G[now][0]);
	postParse(G[now][1]);
	cout << " " << now;
}



int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back(b);
		G[a].push_back(c);

		if (b != -1) {
			in[b]++;
		}
		if (c != -1) {
			in[c]++;
		}
	}


	//root探し
	int root = 0;
	for (int i = 0; i < n; i++)
	{
		if (in[i] == 0) {
			root = i;
			break;
		}
	}

	cout << "Preorder" << endl;
	preParse(root);
	cout << endl;

	cout << "Inorder" << endl;
	inParse(root);
	cout << endl;

	cout << "Postorder" << endl;
	postParse(root);
	cout << endl;
	
	return 0;
}