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

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

트리를 전위 순회한 결과를 입력으로 주어졌을 때, 단순히 후위 순회한 결과만 보여주면 되는 문제이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int temp = Integer.parseInt(s);
        Chain chain = new Chain(temp);
        s = br.readLine();
        while (s != null && !s.isEmpty()) {
            temp = Integer.parseInt(s);
            chain.add(new ChainNode(temp));
            s = br.readLine();
        }
        chain.postOrder(chain.root);
    }
}


class Chain {
    ChainNode root;

    Chain(int v) {
        this.root = new ChainNode(v);
    }

    void add(ChainNode n) {
        ChainNode chain = explore(this.root, n);
        if (chain.value > n.value) {
            chain.left = n;
        } else {
            chain.right = n;
        }
    }

    ChainNode explore(ChainNode start, ChainNode n) {
        int value = n.value;
        int rValue = start.value;
        if (value < rValue) {
            if (start.left != null) {
                return explore(start.left, n);
            } else return start;
        } else {
            if (start.right != null) {
                return explore(start.right, n);
            } else return start;
        }
    }

    void postOrder(ChainNode target) {
        if (target.left != null) {
            postOrder(target.left);
        }
        if (target.right != null) {
            postOrder(target.right);
        }
        System.out.println(target.value);
    }
}

class ChainNode {
    int value;
    ChainNode left;
    ChainNode right;

    ChainNode(int v) {
        this.value = v;
    }
}

 

입력으로 주어진 값을 트리에 담고, 단순하게 후위순회하며 출력했다.

 

트리의 순회 방법은 3가지가 있다.

1. 전위 순회

 전위 순회(Preorder) 는 루트 -> 왼쪽 -> 오른쪽의 순서로 트리를 읽어나가는 것을 의미한다.

2. 중위 순회

 중위 순회(Inorder)는 왼쪽 -> 루트 -> 오른쪽의 순서로 트리를 읽어나가는 것이다.

3. 후위 순회

 후위 순회(Postorder)는 왼쪽 -> 오른쪽 -> 루트의 순서로 트리를 읽어나가는 것을 의미한다.

 

생각대로 트리를 짰는데 문제는 맞춰서 좋지만 좀 더 효율적으로 짤 수 있는 방법을 더 알아봐야할 것 같다.