[백준 C++] 5639 이진 검색 트리 - 트리

5639번: 이진 검색 트리

#include <iostream>
using namespace std;

int Tree[10001];

void DFS(int Current, int End)
{
	if (Current > End)
	{
		return;
	}
	
	int Mid = End + 1;
	for (int i = Current + 1; i <= End; ++i)
	{
		if (Tree[i] > Tree[Current])
		{
			Mid = i;
			break;
		}
	}

	DFS(Current + 1, Mid - 1);
	DFS(Mid, End);
	cout << Tree[Current] << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int i = 0;
	while (true) { cin >> Tree[i]; if (Tree[i] == 0) break; ++i; }

	DFS(0, i - 1);
}

---

 

이진 트리 문제입니다.

 

전위 순회 결과가 입력으로 주어지기 때문에

첫 입력인 루트 노드를 기준으로 왼쪽 서브 트리가 쭉 입력되다가

루트 노드보다 큰 값이 나오면,

그때 부터 쭉 오른쪽 서브 트리가 입력되는 것을 알 수 있습니다.

 

이런식으로 재귀로 왼쪽, 오른쪽 서브 트리를 깊이 우선 탐색해준 다음,

빠져나오면서 각 노드를 출력해주면 후위 순회한 결과를 도출할 수 있습니다.