[트리] 이진 검색 트리 - Gold 4

[jusung-c]

문제 링크

https://www.acmicpc.net/problem/5639

문제 조건

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

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

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

---

아이디어

1. 일단 노드 클래스를 만들고, 이진 검색 트리에 맞게 insert 메서드를 작성한다.
2. 전위 순회는 노드 - 왼쪽 - 오른쪽 순으로 탐색하므로 제일 처음 노드가 부모 노드일 것이다. 주어진 값들을 insert 메서드를 통해 이진 검색 트리로 나타낸다.
3. 만들어진 이진 검색 트리를 후위순회하면 끝

---

구현

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static Node root;
    static class Node {
        int num;

        Node left, right;

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

        public void insertNode(int n) {
            if (n < this.num) {
                if (this.left == null) this.left = new Node(n);
                else this.left.insertNode(n);
            } else {
                if (this.right == null) this.right = new Node(n);
                else this.right.insertNode(n);
            }
        }
    }

    public static void init() throws IOException {
        root = new Node(Integer.parseInt(br.readLine()));

        String input;
        while ((input = br.readLine()) != null && !input.equals("")) {

//            System.out.println(Integer.parseInt(input));
            root.insertNode(Integer.parseInt(input));
        }
    }

    private static void pro() throws IOException {
        backDfs(root);
    }

    private static void backDfs(Node node) throws IOException {
        if (node == null) return;

        backDfs(node.left);
        backDfs(node.right);
        bw.write(node.num +" ");
        bw.newLine();
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}