[백준 5639] 이진 검색 트리

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

#include <cstdio>
#include <unordered_map>
#include <vector>
int root = -1;

struct _st
{
	int l;
	int r;
};

using namespace std;

unordered_map<int, _st> Tree;
vector<int> V;

void input()
{
	int n = 0;
	while (scanf("%d", &n) != EOF) {	// 파일이 끝날 때 까지 받는다. 	// c++의 경우 cin >> n 해주면 됨
		V.push_back(n);
	}
	//printf("%d", V.size());
}


void search(int n, int s, int e)
{
	if (s > e) return;
	
	int m = 0;
	for (m = s; m <= e; m++) {
		if (V[m] > n) break;		// 전위순회이므로 왼쪽 서브트리를 모두 탐색한 후에 오른쪽 서브트리를 탐색한다. 
	}

	if (s <= m - 1) {		// 왼쪽 서브트리 
		Tree[n].l = V[s];	// 현재 노드의 왼쪽에 해당 노드 표시
		Tree.insert({ V[s], {-1, -1} });	// 트리에 삽입
		search(V[s], s + 1, m - 1);			// 해당 노드를 루트로 하는 서브트리 탐색 
	}
	if (m <= e) {			// 오른쪽 서브트리
		Tree[n].r = V[m];	// 현재 노드의 오른쪽에 해당 노드를 표시
		Tree.insert({ V[m], {-1, -1} });	// 트리에 삽입
		search(V[m], m + 1, e);				// 해당 노드를 루트로 하는 서브트리 탐색
	}
}


void make_tree()
{
	root = V[0];	// "전위순회" 이므로 가장 처음 받은 노드가 최상단 루트이다. 
	Tree.insert({ root, {-1, -1} });	// 트리에 삽입
	search(root, 1, V.size() - 1);		// vector의 1번 인덱스부터 마지막 인덱스까지 탐색
}


void post_order(int n)
{
	auto iter = Tree.find(n);
	if (iter->second.l != -1) post_order(iter->second.l);
	if (iter->second.r != -1) post_order(iter->second.r);
	printf("%d\n", n);
}


int main()
{
	input();
	make_tree();
	post_order(root);
	return 0;
}

아.. 트리는 나를 신나게 해 ^^ ! 싸우자 !

 

// input( ) 함수

입력부터 말하지 아니할 수 없다. 처음 보자마자 '그래서 몇개를 입력받으라는건지... '라고 생각하게 한.. 의문의 문제... ㅋㅋㅋㅋ 

알고보니 파일의 마지막까지 입력받는 것이었다.

// <cstdio> header를 쓰는 경우
while (scanf("%d", &n) != EOF){
	V.push_back(n);
}


// <iostream> header를 쓰는 경우
while (cin >> n) {
	V.push_back(n);
}

이때, 몇 개의 수를 입력받을지 알 수 없기 때문에 벡터 컨테이너를 사용해야 한다. 

 

 

// make_tree( ) 함수

해당 함수는 이진 검색 트리를 생성한다. 

문제에서 입력받는 수는 전위순회한 결과이기 때문에 "최상단 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리" 순서로 탐색을 진행한다. 

따라서 벡터에 가장 처음 담긴 숫자(V[0])가 루트가 되고, 아직 왼쪽 노드와 오른쪽 노드를 모르기 때문에 {-1, -1}이라고 추가해준다. 

이제 search 함수를 통해 현재 노드인 루트에 대하여 인덱스 1부터 (0은 루트임) 벡터의 끝까지 탐색하며 트리를 생성한다. 

 

 

// search( ) 함수

만약 시작 인덱스 s가 끝 인덱스 e보다 커지면 탐색을 종료한다. 

한편, 문제에서 입력받는 수는 전위 순회한 결과이기 때문에 최상단 루트노드를 기준으로 왼쪽에 있는 모든 수가 입력된 다음 오른쪽에 있는 모든 수가 입력된다. 이때 특징은 왼쪽 서브트리의 모든 수들은 루트노드보다 크기가 작다는 것이며, 오른쪽 서브트리의 모든 수들은 루트노드보다 크기가 크다. 

따라서 루프를 돌며 벡터의 m번째 원소가 현재 노드 n보다 커질 때를 확인한다. 

 

벡터의 시작인덱스 s가 m - 1(왼쪽 서브트리의 마지막 원소의 인덱스)보다 같거나 작으면 왼쪽 서브트리의 멤버이다. 따라서 노드 n의 왼쪽에 V[s]를 표시하고, 트리에 삽입한다. 

다음으로 해당 노드(V[s])를 루트로 하는 서브트리를 탐색한다. 

 

인덱스 m이 마지막 인덱스 e보다 작거나 같으면 오른쪽 서브트리의 멤버이다. 따라서 노드 n의 오른쪽에 V[m]를 표시하고, 트리에 삽입한다. 

다음으로 해당 노드(V[m])을 루트로 하는 서브트리를 탐색한다. 

 

 

// post_order( ) 함수

문제에서 해당 트리를 후위순회한 결과를 출력해야 하기 때문에 "왼쪽 서브트리 -> 오른쪽 서브트리 -> 최상단 루트노드" 순서로 탐색을 진행해야 한다. 

따라서 파라미터로 받은 노드의 왼쪽 자식노드가 존재하면 재귀함수를 콜하여 왼쪽 서브트리를 탐색하고, 오른쪽 자식노드가 존재하면 재귀함수를 콜하여 오른쪽 서브트리를 탐색한다.