[Algorithm] 백준/5639 :: 이진 검색 트리

* 핵심

BinaryTree Class를 만들어서 left, right에 자식 이진 트리를 만들어 붙여 트리를 만든다.

* 문제

문제

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

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

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

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

입력

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

출력

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

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BinaryTree tree = new BinaryTree(Integer.parseInt(br.readLine()));
        String s = "";
        while ((s = br.readLine()) != null && s.length() != 0) {    //EOF까지 입력받음
            tree = tree.addTree(tree, Integer.parseInt(s));
        }
        postorder(tree);
        System.out.println(sb);
    }
 
    public static void postorder(BinaryTree tree) {
        if (tree.left != null) postorder(tree.left);
        if (tree.right != null) postorder(tree.right);
        sb.append(tree.data + "\n");
    }
}
 
class BinaryTree {
    int data;
    BinaryTree left;
    BinaryTree right;
 
    public BinaryTree(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
 
    public BinaryTree addTree(BinaryTree tree, int val) {
        BinaryTree curTree = null;
        if (tree == null) return new BinaryTree(val);
        if (tree.data > val) {
            curTree = addTree(tree.left, val);  //새로운 하위 이진 트리 생성
            tree.left = curTree;                //부모 노드의 왼쪽에 붙인다
        } else if (tree.data < val) {
            curTree = addTree(tree.right, val); //새로운 하위 이진 트리 생성
            tree.right = curTree;               //부모 노드의 오른쪽에 붙인다
        }
        return tree;                            //새로 붙인 트리 return
    }
}