[알고리즘] 이진 검색 트리(백준5639번)_골드5_트리순회, 전위순회, 후위순회, 이진트리, 이진 검색 트리

문제링크

📝 문제

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

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

50
30
24
5
28
45
98
52
60

 

예제 출력 1

5
28
24
45
30
60
52
98
50

---

🔍 정답

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

public class Main {
    public static class Tree {
        /**
         * @num 노드 번호
         * 해당 노드 번호의 left와 right도 각각 객체로 저장한다.
         */
        int num;
        Tree left, right;

        public Tree(final int num) {
            this.num = num;
        }

        /**
         * 입력받은 값이 현재 값(this.num)보다 작으면 왼쪽 노드를 확인하고, 왼쪽 노드가 있다면 왼쪽 노드의 자식 노드가 된다.
         * (오른쪽 노드 없이 왼쪽 노드만 연속으로 입력받는 경우)
         * 입력받은 값이 현재 값보다 크면 오른쪽 노드를 확인하고, 오른쪽 노드가 존재하면 오른쪽 노드의 자식 노드가 되고
         * 없다면 오른쪽 노드가 된다. (왼쪽 노드 없이 오른쪽 노드만 연속으로 입력받는 경우)
         */
        public void node(final int num) {
            if (num < this.num) {
                if (this.left == null) {
                    this.left = new Tree(num);
                } else
                    this.left.node(num);
            } else {
                if (this.right == null) {
                    this.right = new Tree(num);
                } else
                    this.right.node(num);
            }
        }
    }

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

        // 처음 입력값은 루트 노드이므로 따로 입력받기
        Tree tree = new Tree(Integer.parseInt(br.readLine()));

        /**
         * @while 입력값이 null이거나 공백일 때 종료
         */
        while (true) {
            String input = br.readLine();
            if (input == null || input.equals("")) break;

            tree.node(Integer.parseInt(input));
        }

        // 후위 순회
        postOrder(tree);
    }

    /**
     * 루트 노드부터 시작해서 트리의 왼쪽이 존재하면 재귀로 타고 내려간다.
     * 자식 노드가 없는 곳까지 가서 출력을 시작한다.
     */
    public static void postOrder(Tree tree) {
        if (tree.left != null) {
            postOrder(tree.left);
        }
        if (tree.right != null) {
            postOrder(tree.right);
        }
        System.out.println(tree.num);
    }
}

• 참고사이트
• 트리를 어떻게 구성해야될지 고민이 많았다.
• 2차원 배열을 만들어서 arr[깊이][노드위치(왼, 오)] 를 저장한 후에 가장 깊은 배열에서부터 출력을 하는 방법으로 해보려고 했으나 깊이가 깊어질 수록 노드위치의 수가 엄청 많아질 수가 있고 구분이 어려웠다.
• ArrayList<Integer>[] 에 자식 노드를 저장하는 방법, 부모 노드를 저장하는 방법도 생각해보았는데 List가 천 개 단위를 넘어갈 수도 있었고 노드의 키 값이 제각각이라 이것도 구현이 어려울 것 같았다.
• 클래스를 만들어서 node번호와 자식 노드 혹은 부모 노드를 저장하는 방법을 생각했는데 자식 노드 혹은 부모 노드를 객체가 아니라 node 번호로 저장할 생각만 하다보니 구현이 마땅치 않았던 것 같다.
• 몇 시간을 헤매다가 참고 사이트를 보고 속이 뻥 뚫렸는데, 답안을 보고나니 구현은 어렵지가 않았다. 그만큼 객체를 다루는 실력이 아직 미숙하다는 의미인 것 같다 ㅠㅠ
• 풀이법은 루트 노드부터 시작해서 각각 왼쪽과 오른쪽 노드를 객체로 저장하는 것이고 가장 왼쪽 끝 노드를 시작으로 순차적으로 출력을 하는 것이다.

• toString() 메서드를 만들어서 출력해보면 트리는 이런 식으로 구성이 된다.
• 보기가 좀 이쁘지가 않지만, 50의 왼쪽 노드로 30이 있고 30의 왼쪽 노드로 24, 그 왼쪽 노드로 5가 있으며 5는 리프 노드가 된다. 그리고 다시 24의 오른쪽 노드로 28이 존재하는 식이다.