백준 - 5639 이진 검색 트리(Java)

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

5639번: 이진 검색 트리

 

탐색 문제입니다.

 

전위 탐색 정보를 사용하여, 후위 탐색 정보를 출력해야 합니다.

전위 탐색은 다음과 같습니다.

void pre(Node node){
    print(node);
    pre(node.left);
    pre(node.right);
}

즉, 전위 탐색은 현재 노드를 출력하고 좌측부터 탐색을 하는 방법입니다.

때문에, 입력에서 주어지는 첫 번째 입력은 루트 노드라는 것을 알 수 있습니다.

루트 노드 이후에 주어지는 입력은 루트 노드의 하위 노드들로, 이진 검색 트리 조건에 맞에 삽입(insert)하면 됩니다.

 

 

[구현 코드]

import java.io.*;

public class Main {

    private static class Node {
        int number;
        Node left, right;

        public Node(int number) {
            this.number = number;
        }

        void insert(int input) {
            // 삽입 노드가 현재 노드보다 작을 때(왼쪽 삽입)
            if (this.number > input) {
                if(this.left == null) {
                    this.left = new Node(input);
                }else{
                    this.left.insert(input);
                }
            }
            // 삽입 노드가 현재 노드보다 클 때(오른쪽 삽입)
            else{
                if(this.right == null){
                    this.right = new Node(input);
                }else {
                    this.right.insert(input);
                }
            }

        }
    }

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

        // 루트 노드
        Node node = new Node(Integer.parseInt(br.readLine()));

        // 하위 노드
        while (true) {
            String read = br.readLine();
            if (read == null || read.equals("")) break;

            int input = Integer.parseInt(read);
            node.insert(input);
        }

        post(node, bw);

        bw.flush();
        bw.close();
        br.close();
    }

    // 후위 탐색
    private static void post(Node node, BufferedWriter bw) throws IOException {
        if(node.left != null) post(node.left, bw);
        if(node.right != null) post(node.right, bw);
        bw.write(node.number + System.lineSeparator());
    }
}