[백준] 5639번 이진 탐색 트리 (C++) - binary search tree

발상

우선 전위 탐색을 통해 얻은 tree가 주어지므로, 이를 배열에 입력받는다. 

그리고 아래 그림과 같은 이분 탐색을 거치면, 후위 탐색으로 배열을 바꿀 수 있다.

 

전위 탐색 : root -> left -> right

후위 탐색 : left -> right -> root 이므로

순서를 바꾸어준다. 

소스코드

#include <iostream>
#include <vector>

using namespace std;

int tree[10001];

void postorder(int start, int end){
	if(start == end) {
		cout << tree[start] << "\n";
		return;
	}
	if(start>end) return;
	int i = start+1;
	while(true){
		if(tree[start]<tree[i] || i>end){
			break;
		}
		i++;
	}
	postorder(start+1,i-1);
	postorder(i,end);
	cout << tree[start] << "\n";

}
int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	
	int num;
	int count = 0;
	while(cin >> num){
		tree[count++] = num;
	}
	postorder(0, count-1);
	return 0;
}

 

search하는 재귀함수 postorder만 살펴보면 다음과 같다. 

 

void postorder(int start, int end){
	if(start == end) {
		cout << tree[start] << "\n";
		return;
	}
	if(start>end) return;
	int i = start+1;
	while(true){
		if(tree[start]<tree[i] || i>end){
			break;
		}
		i++;
	}
	postorder(start+1,i-1);
	postorder(i,end);
	cout << tree[start] << "\n";

}

strart와 end를 받아주고,

1) tree의 start와 end가 같으면 해당 tree를 출력해준다. (tree의 크기가 1) 그리고 return하여 탐색을 종료한다.

2) tree의 start보다 end가 작으면 탐색을 종료한다. 

3) 둘 다 해당하지 않는 경우: tree[start]와 start+1부터의 요소의 크기를 비교하여 tree보다 큰 지점이 나오면 탐색을 종료한다. 이 떄의 i가 처음 tree보다 큰 값이 등장하는 node이므로, 

postorder(start+1, i-1)

postorder(i, end)

를 수행하여 left -> right 순으로 탐색해 준다.

마지막으로 root를 출력한다.