[백준] 5639: 이진 검색 트리

SuKong·2020년 8월 24일

백준 알고리즘 재귀 트리

BOJ의 알고리즘 문제를 풀어보아요

목록 보기

41/49

'5639- 이진 검색 트리' 문제로 이동!

👉문제

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

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

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

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

👉입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

예시 -
50
30
24
5
28
45
98
52
60

👉출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예시 -
5
28
24
45
30
60
52
98
50

✍내 풀이

import java.io.*;
import java.util.*;

public class Main {	
	static Node root;
	static ArrayList<Integer> postorderArr;
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		postorderArr = new ArrayList();
		root = new Node(Integer.parseInt(bf.readLine()));
		String str = null;
		while((str = bf.readLine()) != null && str.length() != 0) {
			Node node = new Node(Integer.parseInt(str));
			putNode(root, node); 
		}
		
		postorder(root);
		for(int i : postorderArr)
			System.out.println(i);
		
	}
	
	static void postorder(Node node) {
		if(node.left != null)
			postorder(node.left);
		if(node.right != null) 
			postorder(node.right);
		postorderArr.add(node.name);
	}
	
	static void putNode(Node startNode, Node inputNode) {
		if( startNode.name > inputNode.name) {
			if( startNode.left != null) {
				putNode(startNode.left, inputNode);
			}else {
				startNode.left = inputNode;
			}
		}
		if( startNode.name < inputNode.name) {
			if( startNode.right != null) {
				putNode(startNode.right, inputNode);
			}else {
				startNode.right = inputNode;
			}
		}
	}
}

class Node{
	int name;
	public Node(int name){
		this.name = name;
	}
	Node left;
	Node right;
}

✍Note

트리의 구조를 활용하는 문제 -> Node클래스를 선언해서 객체활용

⭐입력이 끝날 때까지 입력받기

BufferedReader 활용 :

while((str = bf.readLine()) != null && str.length() != 0)

위의 조건문으로 버퍼에 저장되는 값이 존재하지 않을 때까지 입력받음.
( readLine() 과 read()를 동시에 사용하지X )

⭐노드 삽입

putNode ( Node 기준노드, Node 삽입할 노드 ) :

기준 노드와 삽입할 노드의 숫자를 비교해서 문제에서 주어진 조건에 만족하도록 삽입
if( 기준 노드의 숫자 < 삽입 노드의 숫자 )
=> 기준 노드의 오른쪽에 위치해야함
=> 기준 노드의 오른쪽 자식이 있는 경우 putNode( 기준노드.right , 삽입할 노드 ) 로 재귀 호출
=> 기준 노드의 오른쪽 자식이 없는 경우 기준노드.right = 삽입할 노드
반대의 경우도 마찬가지로 삽입