[백준] 5639번 : 이진 검색 트리 - 자바[Java]

5639번: 이진 검색 트리

풀이

<트리 자료구조 생성>

Node 클래스를 생성하고, 클래스 내에 int value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다.

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

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

static 변수로 루트 노드 Node root을 생성한다.

    static Node root; //트리의 루트 노드

입력을 받을 때마다 createNode() 함수를 호출하고, root가 null이면 root 노드를 생성하고, root가 이미 있다면 insertNodePreOrder() 함수를 호출하여 올바른 위치에 노드를 삽입한다.

    static void createNode(int n) {
        if (root == null) {
            root = new Node(n);
        }
        else insertNodePreOrder(root, n);
    }

    static void insertNodePreOrder(Node node, int value) {
        if (node.value < value) {
            if (node.right == null) {
                node.right =  new Node(value);
            }
            else
                insertNodePreOrder(node.right, value);
        }
        else if (node.value > value) {
            if (node.left == null) {
                node.left =  new Node(value);
            }
            else
                insertNodePreOrder(node.left, value);
        }
    }

그 후 트리를 후위 순회를 한 결과를 출력하면 된다.

 

주의할 점

• 트리를 전위 순회한 결과를 입력으로 받을 때, null이 주어지면 입력을 받는 것을 중단해야 한다. 

 

코드

import java.io.*;

public class Main {

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

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

    static Node root; //트리의 루트 노드
    static StringBuilder sb = new StringBuilder();  //출력 결과

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            String input = br.readLine();
            if (input == null)
                break;

            int n = Integer.parseInt(input);
            createNode(n);
        }

        postOrder(root); //후위 순회
        sb.append("\n");

        System.out.println(sb);
    }

    static void createNode(int n) {
        if (root == null) {
            root = new Node(n);
        }
        else insertNodePreOrder(root, n);
    }

    static void insertNodePreOrder(Node node, int value) {
        if (node.value < value) {
            if (node.right == null) {
                node.right =  new Node(value);
            }
            else
                insertNodePreOrder(node.right, value);
        }
        else if (node.value > value) {
            if (node.left == null) {
                node.left =  new Node(value);
            }
            else
                insertNodePreOrder(node.left, value);
        }
    }

    static void postOrder (Node node) {
        if (node == null) return;

        postOrder(node.left);
        postOrder(node.right);
        sb.append(node.value).append("\n");
    }

}