재귀 없이 트리 preorder 순회하기

재귀 없이 트리를 순회하는 방법은 스택을 이용하는 것이다. 먼저 root를 넣고 왼쪽 자식과 오른쪽 자식을 탐색하게 된다. 오른쪽 자식이 나중이므로 stack에는 먼저 push를 하는 점을 유의해야 한다

 

#include <stack>
#include <iostream>

using namespace std;

int tree[30][2];

void preorder(int root) {
	stack<char> st;
	st.push(root);

	while (!st.empty()) {
		int t = st.top();
		st.pop();

		cout << (char)('A' + t);
		if (tree[t][1] > -1) {
			st.push(tree[t][1]);
		}
		if (tree[t][0] > -1) {
			st.push(tree[t][0]);
		}
	}
	cout << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char a, b, c;
		cin >> a >> b >> c;
		int p = a - 'A';
		int c1, c2;
		if (b == '.') c1 = -1;
		else c1 = b - 'A';
		if (c == '.') c2 = -1;
		else c2 = c - 'A';
		tree[p][0] = c1;
		tree[p][1] = c2;
	}

	preorder(0);
	return 0;
}