8. 트리의 구현과 순회 - 트리 순회 순서 변경(traversal) 문제

 

이 문제는 재귀 호출을 이용하면 간단하게 구현할 수 있다.

전위 순회 순서에서 가장 먼저 오는 값은 트리의 루트값이라는 것을 알 수 있다.

그러면 이 값을 중위 순회에서 찾아 왼쪽 서브트리와 오른쪽 서브트리를 구분할 수 있게 된다.

 

위와 같이 왼쪽 서브트리의 크기를 구하여 전위 순회 배열과 중위 순회 배열을 잘라 재귀호출 할 수 있다.

 

 

// 트리 순회 순서 변경 문제를 해결하는 재귀 호출 코드
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// v 벡터를 a인덱스부터 b-1인덱스까지 자른 결과 리턴
vector<int> slice(const vector<int>& v, int a, int b) {
	return vector<int>(v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
	int n = preorder.size();  // 현재 트리의 노드의 개수

	// 현재 트리가 비어있으면 종료
	if (n == 0) return;

	// 현재 트리의 루트 노드는 전위 결과의 0번째 인덱스 값
	int root = preorder[0];

	// 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아 알아낼 수 있다.
	int lSize = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	int rSize = n - 1 - lSize;

	// 재귀 호출을 통해 왼쪽 서브트리부터 출력한다.
	printPostOrder(slice(preorder, 1, lSize + 1), slice(inorder, 0, lSize));
	printPostOrder(slice(preorder, lSize + 1, n), slice(inorder, lSize + 1, n));
	cout << root << " ";

	return;
}

int main() {
	int c;  // 테스트 케이스 수
	cin >> c;

	for (int test = 0; test < c; test++) {
		int num;  // 노드의 수
		cin >> num;
		vector<int> preorder(num);
		vector<int> inorder(num);

		for (int i = 0; i < num; i++) {
			cin >> preorder[i];
		}
		for (int i = 0; i < num; i++) {
			cin >> inorder[i];
		}

		printPostOrder(preorder, inorder);
		cout << endl;
	}
	return 0;
}