이진 검색 트리 (백준 5639번)

전위순회 결과를 바탕으로 트리를 만들고, 후위순회를 출력하면 된다.

 

풀이 순서

1. 입력을 바탕으로 트리를 구성. (노드 클래스를 활용)

2. 노드 클래스 내부에 insert 함수 작성.

insert 함수 : 입력된 노드의 값을 현재 노드 값과 비교하여, 왼쪽 혹은 오른쪽에 달아주는 함수.

 

이때 insert 함수에 재귀함수를 적용해야 한다.

• 해당 위치가 비어있으면 해당 위치에 노드를 달아주고,
• 비어있지 않다면 해당 위치에 있는 노드의 insert함수를 재귀호출

 

코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

public class Main {

    // BOJ 5639번 이진 검색 트리
   
    static class Node{
        int num;
        Node left, right;
        public Node(int num){
            this.num = num;
        }

        public void insert(Node input){
            if(this.num > input.num){ // 왼쪽
                if(this.left == null){ // 비어있으면 달아주기
                    this.left = input;
                }else{ // 비어있지 않으면 재귀호출
                    this.left.insert(input);
                }
            }else { // 오른쪽
                if(this.right == null){ // 비어있으면 달아주기
                    this.right = input;
                }else{ // 비어있지 않으면 재귀호출
                    this.right.insert(input);
                }
            }
        }

    }

    static void solve(Node node){
        if(node!=null){
            solve(node.left);
            solve(node.right);
            System.out.println(node.num);
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Node root = new Node(Integer.parseInt(br.readLine()));

        while(true){
            String input = br.readLine();
            if(input==null || input.equals("")) break;
            int n = Integer.parseInt(input);
            root.insert(new Node(n));
        }

        solve(root);

    }

}

문제

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

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

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

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

입력

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

출력

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