[JAVA] 백준 q5639 - 이진 검색 트리

5639번: 이진 검색 트리

---

> 의식의 흐름

트리 만들구 후위 순회하면 되겠징,,,

> 풀이 과정

1. 첫번째 입력값을 루트노드로 지정한다.

2. 이후 입력값들에 대해 루트노드를 기준으로 트리를 생성한다.

• 왼쪽, 오른쪽 Node를 담는 Node 클래스 이용 

3. 입력 없을 때까지 2번 과정 반복한다.

while((input=br.readLine()) != null && !input.isEmpty()){ 
  // 2번 과정
}

4. 후위 순회 후 결과 출력한다.

• 후위 순회 시, 왼쪽 노드 확인 -> 오른쪽 노드 확인 -> 가운데 노드 출력

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static Node rootNode;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value){
            this.value = value;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        rootNode = new Node(Integer.parseInt(br.readLine())); // 루트 노드 설정
        String input = "";
        while((input=br.readLine()) != null && !input.isEmpty()){ // 입력 끝날 때까지
            int value = Integer.parseInt(input);

            addNode(value, rootNode);
        }

        postOrder(rootNode);
        bw.flush();

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

    public static void addNode(int value, Node node){
        if(node.value > value){ // 왼쪽으로 들어가야 하는 경우
            if(node.left == null){ // 왼쪽에 새로운 노드 삽입
                node.left = new Node(value);
                return;
            }

            addNode(value, node.left);
        }
        else{ // 오른쪽으로 들어가야하는 경우
            if(node.right == null){ // 왼쪽에 새로운 노드 삽입
                node.right = new Node(value);
                return;
            }

            addNode(value, node.right);
        }
    }

    public static void postOrder(Node node) throws Exception{ // 후위 순회
        if(node.left != null){
            postOrder(node.left);
        }

        if(node.right != null){
            postOrder(node.right);
        }

        bw.write(Integer.toString(node.value)+"\n");
    }
}