[백준 - 5639] 이진 트리 검색 - Java

문제 설명

 

5639번: 이진 검색 트리

 

접근 방법

해당 문제에서는 이진 트리 구조를 전위 순회한 결과를 순서대로 제공해주고 이 결과를 통해 해당 이진 트리 구조를 후위 순회한 결과를 요구하고 있습니다.

 

우선 해당 문제를 풀기 위해서는 전위 순회(루트 - 왼쪽 노드 - 오른쪽 노드 순 탐색)한 결과만으로 본래 이진 트리 구조를 만드는 것이 급선무였습니다. 이진 트리 구조는 단순하게 특정 노드를 추가할 때 루트 노드를 기준으로 작으면 왼쪽에, 크면 오른쪽에 배치하고 이후 부모 노드와도 동일한 기준으로 배치하면서 만들어지는 구조입니다.

 

이러한 이진 트리 구조 특성을 이용하여 순서대로 주어지는 수를 최초 루트 노드 값과 비교하면서 왼쪽, 오른쪽을 탐색하면서 트리구조를 이루도록 했는데, 이때 Node(노드)라는 별도의 구조체를 만들고, 왼쪽 및 오른쪽을 탐색하는 내용을 재귀를 통해 구현했습니다.

 

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

        Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }

        void addLeft(int data) {
            if (left == null) {
                left = new Node(data);
                return;
            }

            if (left.data > data) {
                left.addLeft(data);
            } else {
                left.addRight(data);
            }
        }

        void addRight(int data) {
            if (right == null) {
                right = new Node(data);
                return;
            }

            if (right.data > data) {
                right.addLeft(data);
            } else {
                right.addRight(data);
            }
        }
    }

 

이를 통해 본래의 이진 트리 구조를 얻어 낸 다음에는 후위 순회를 해주면됩니다. 후위 순회의 경우는 왼쪽 노드, 오른쪽 노드, 상위 노드 순으로 순회하는 것으로서 마찬가지로 재귀 함수를 통해서 구현할 수 있었습니다.

 

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

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

 

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

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

        Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }

        void addLeft(int data) {
            if (left == null) {
                left = new Node(data);
                return;
            }

            if (left.data > data) {
                left.addLeft(data);
            } else {
                left.addRight(data);
            }
        }

        void addRight(int data) {
            if (right == null) {
                right = new Node(data);
                return;
            }

            if (right.data > data) {
                right.addLeft(data);
            } else {
                right.addRight(data);
            }
        }
    }

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

        int rootValue = Integer.parseInt(br.readLine()), number;
        Node root = new Node(rootValue);

        while (br.ready()) {
            number = Integer.parseInt(br.readLine());

            if (rootValue > number) {
                root.addLeft(number);
            } else {
                root.addRight(number);
            }
        }

        postOrder(root);
    }

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

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }
}

 

 

참고자료

• https://readerr.tistory.com/35
• https://www.acmicpc.net/problem/5639