(Java/자바) - 백준(BOJ) 5639번 : 이진 검색 트리

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

5639번: 이진 검색 트리

---

• 문제 : 

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

 

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

BST 문제였습니다.

 

전위순회의 결과를 보고 후위순회로 출력하면 됩니다.

 

우선, 노드의 개수가 주어지지 않고 EOF 까지의 입력을 처리해주기 위해 아래와 같은 구문을 사용하였습니다.

아래 구문은 BufferedReader를 사용했을 때 EOF 처리를 하는 방법입니다.

Scanner엔 hasNext()라는 메서드를 사용하면 된다고 합니다.

 

String input;

while((input = br.readLine()) != null){
	......
}

 

tree 배열에 주어진 input을 모두 삽입한 뒤 후위순회 함수를 호출합니다. 

 

전위순회로 입력받은 배열의  가장 앞 노드는 항상 해당 서브트리의 루트노드입니다.

또한, 이진탐색트리의 특성상 루트노드의 key값을 기준으로 그보다 작은 값들은 왼쪽, 그보다 큰 값들은 오른쪽 서브트리의 노드들입니다.

 

따라서, 우리는 다음과 같은 작업을 해야합니다.

초기 start = 0, end = 마지막 노드(배열의 길이)

1. start ~ end 범위의 배열(트리)에서 루트노드를 찾음, 이는 tree[start]로 접근 가능.

 

2. tree[start]의 키값을 기준으로 start + 1부터 그보다 작은 노드들의 개수를 찾음.

 

3. start = start + 1, end = tree[start]보다 큰 노드가 나오는 첫 인덱스로 지정하고 1로 돌아가서 반복

( tree[start]보다 큰 노드가 나오는 인덱스는 원래 루트노드가 위치해야 할, 왼쪽 서브트리와 오른쪽 서브트리를 나누는 경계선입니다.)

 

4. start == end일 때 함수 종료.  

 

 

---

• 소스코드 : 

package algorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BOJ_5639_이진검색트리_576ms {
	static int[] tree = new int[10000];
	static void postOrder(int start, int end) {
		int i;
		if (start >= end) {
			return;
		}
		for (i = start+1; i < end; i++) {
			if(tree[start] < tree[i] )break;
		}
		postOrder(start+1, i);
		postOrder(i, end);
		System.out.println(tree[start]);
		return ;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i = 0;
		String input;
		// 입력받기
		while((input = br.readLine()) != null) tree[i++] = Integer.parseInt(input);
		
		// 후위순회 호출
		postOrder(0, i);
	}
	
}