BOJ_5639 : 이진 검색 트리

👉 문제링크

---

---

🔸 문제 분석 🔸

• 이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력한다.

🔸 문제 풀이 🔸

• 전위 순회 결과를 EOF(End Of File : null)가 나올 때까지 입력받는다.
  • 첫 번째 결과는 Root 로 사용한다.
  • 이후 결과는 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 구분해 재귀 메서드를 호출하고 저장한다.
• 전위 순회 결과로 만들어진 이진 검색 트리를 후위 순회 방식으로 재탐색하여 결과를 출력한다.
  • 전위 순회와 비슷하지만, 탐색 순서만 변경하면 된다.

🔸 코드 🔸

import java.io.*;

public class Main {
    private static class Node {
        private final int root;
        private Node left;
        private Node right;

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

        public int getRoot() {
            return root;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

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

        Node root = new Node(Integer.parseInt(br.readLine()));

        String str = null;

        // Pre Order

        while ((str = br.readLine()) != null) {
            make_tree(root, Integer.parseInt(str));
        }

        // Post Order

        StringBuilder sb = new StringBuilder();

        travel_tree(root, sb);

        // Output
        bw.write(sb.toString());
        bw.flush();
    }

    private static void make_tree(Node node, int num) { // Pre order
        if (node.getRoot() > num) { // left
            if (node.getLeft() == null) {
                node.setLeft(new Node(num));
            } else {
                make_tree(node.getLeft(), num);
            }
        } else { // right
            if (node.getRight() == null) {
                node.setRight(new Node(num));
            } else {
                make_tree(node.getRight(), num);
            }
        }
    }

    private static void travel_tree(Node node, StringBuilder sb) { // Post order
        // left
        if (node.getLeft() != null) {
            travel_tree(node.getLeft(), sb);
        }

        // right
        if (node.getRight() != null) {
            travel_tree(node.getRight(), sb);
        }

        // root
        sb.append(node.getRoot()).append('\n');
    }
}

🔸 코드 해석 🔸

• 이진 검색 트리를 구현하기 위해 Node 클래스를 만들어 사용했다.
  • 현재 노드 값인 int형 변수 root와 왼쪽 자식, 오른쪽 자식을 저장할 Node 객체 left, right를 사용했다.
  • getter, setter를 사용해보았다.
• 전위 순회 결과를 토대로 이진 검색 트리를 생성한다.
  • 첫 결과 값은 Node 객체 root로 저장해 탐색을 시작 할 때마다 사용한다.
  • 다음 결과 값 부터는 make_tree() 메서드를 호출해 Node의 root 값보다 작으면 left, 크면 right로 저장한다.
  • left, right 객체가 생성 되지 않은 null이라면 탐색을 종료하고 해당 Node 객체를 생성해 저장한다.
• 후위 순회는 시작 root 노드부터 left, right, root값 순으로 탐색해 StringBuilder에 저장한다.
  • travel_tree() 메서드의 재귀 방식으로 탐색한다.
• 최종 탐색 결과인 StringBuilder값을 출력한다.

---

🔸 end 🔸

• 오랜만에 다시 시작하는 백준 코테 풀이인데 골드만 풀 계획이고, 스트릭을 이어나가 볼 생각이다.
  • Solved.ac의 Class 문제도 풀면서, 코테 교재 문제도 따라 풀 생각이고, 알고리즘마다 대표 문제들을 선정해놔서 같은 문제를 반복으로 푸는 연습도 해볼 생각이다.
• 위 문제는 Node 클래스와 재귀 메서드만 구현할 줄 알면 간단히 풀이할 수 있는 것 같다.