[05. 재귀 알고리즘] 전위/중위/후위 순회

Recursion

#include <iostream>
using namespace std;

void inorder_recur(int n) {		// 중위
	if (n <= 0) return;

	inorder_recur(n - 1);
	cout << n << ' ';
	inorder_recur(n - 2);
}

int main() {
	inorder_recur(4);
}

void preorder_recur(int n) {	// 전위
	...
	cout << n << ' ';
	preorder_recur(n - 1);
	preorder_recur(n - 2);
}

void postorder_recur(int n) {	// 후위
	...
	postorder_recur(n - 1);
	postorder_recur(n - 2);
    cout << n << ' ';
}

Recursion + Memoization

#include <iostream>
#include <vector>
using namespace std;

void inorder_recur(int n) {		// 중위
	if (n <= 0) return;
	
	static vector<string> memo(n + 2);
	// inorder_recur 함수를 main에서 두 번 이상 호출시 필요
    //if (n + 2 > (int)memo.size())
	//	memo.resize(n + 2);

	if (!memo[n+1].empty())
		cout << memo[n+1];
	else {
		inorder_recur(n - 1);
		cout << n << ' ';
		inorder_recur(n - 2);
		memo[n+1] = format("{}{} {}", memo[n], n, memo[n-1]);	// since C++20
	}
}

int main() {
	inorder_recur(4);
}

void preorder_recur(int n) {	// 전위
	...
	cout << n << ' ';
	preorder_recur(n - 1);
	preorder_recur(n - 2);
    memo[n+1] = format("{} {}{}", n, memo[n], memo[n-1]);
    ...
}

void postorder_recur(int n) {	// 후위
	...
	postorder_recur(n - 1);
	postorder_recur(n - 2);
    cout << n << ' ';
    memo[n+1] = format("{}{}{} ", memo[n], memo[n-1], n);
    ...
}

Stack: 재귀의 제거

#include <iostream>
#include <stack>
using namespace std;

void inorder_stack(int n) {		// 중위
	stack<int> st;

	while (1) {
		while (n > 0)
			st.push(n--);				// while, n--: 재귀 제거
		
		if (st.empty()) break;
		n = st.top();
		st.pop();
		cout << n << ' ';
		
		n -= 2;							// 꼬리재귀 제거
	}
}

int main() {
	inorder_stack(4);
}

• (중위: pop할 때 cout), (전위: push할 때 cout)

#include <iostream>
#include <stack>
using namespace std;

void preorder_stack(int n) {	// 전위
	stack<int> st;

	while (1) {
		while (n > 0) {
			cout << n << ' ';
			st.push(n--);
		}
		
		if (st.empty()) break;
		n = st.top();
		st.pop();
		
		n -= 2;
	}
}

int main() {
	preorder_stack(4);
}

• 후위: 전위에서 n-1, n-2 순서를 n-2, n-1순서로 바꾸고 stack을 이용해 출력순서를 뒤집었다.

#include <iostream>
#include <stack>
using namespace std;

void postorder_stack(int n) {	// 후위
	stack<int> st;
	stack<int> visited;

	while (1) {
		while (n > 0) {
			visited.push(n);
			st.push(n);
			n -= 2;
		}
		
		if (st.empty()) break;
		n = st.top();
		st.pop();
		
		n -= 1;
	}
	while (!visited.empty()) {
		cout << visited.top() << ' ';
		visited.pop();
	}
}

int main() {
	postorder_stack(4);
}

출력

Recursion, Recursion+Memoization, Stack의 결과는 동일하다.

중위

1 2 3 1 4 1 2

전위

4 3 2 1 1 2 1

후위

1 2 1 3 1 2 4