백준 : 이진 트리 순회 #5639 [JAVA]

개인 노션 링크

문제 원본 링크

문제 설명

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

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

• 전위 순회는 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.
• 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.

예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

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

[입력 조건]

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

풀이 과정

트리를 구성하는 노드 클래스

• 각 노드의 data와 자식 노드들을 저장한다.

class Node {
    private int data;
    private Node lNode;
    private Node rNode;

    public int getData() {
        return data;
    }

    public Node getlNode() {
        return lNode;
    }

    public Node getrNode() {
        return rNode;
    }

    public void setlNode(Node node) {
        this.lNode = node;
    }

    public void setrNode(Node node) {
        this.rNode = node;
    }

    public Node(int data) {
        this.data = data;
        setlNode(null);
        setrNode(null);
    }
}

트리를 구성하는 트리 클래스

• 트리는 기본으로 root 노드를 가진다.
• createNode() : 루트 노드를 생성하는 메소드
• traversalNode() : 루트 노드 이외에 노드를 생성하는 메소드
  - 이진 트리 조건에 맞게 적절한 위치에 생성되도록 한다.
• postOrderTraversal() : 후위 순회 방식으로 노드를 출력하는 메소드

class Tree {
    Node root;

    void createNode(int data) {
        if (root == null) {
            root = new Node(data);
            root.setlNode(null);
            root.setrNode(null);
        } else {
            traversalNode(root, data);
        }
    }

    void traversalNode(Node node, int data) {
        if (node.getData() < data) {
            if (node.getrNode() == null) {
                node.setrNode(new Node(data));
            } else {
                traversalNode(node.getrNode(), data);
            }
        } else {
            if (node.getlNode() == null) {
                node.setlNode(new Node(data));
            } else {
                traversalNode(node.getlNode(), data);
            }
        }
    }

    void postOrderTraversal(Node node) {
        if (node != null) {
            if (node.getlNode() != null) postOrderTraversal(node.getlNode());
            if (node.getrNode() != null) postOrderTraversal(node.getrNode());
            System.out.println(node.getData());
        }
    }
}

위에서 만든 클래스들을 구동시키는 메인 클래스

• BufferedReader와 InputStreamReader를 통해 사용자의 입력값을 받는다.
• isNumber() : EOF 여부를 판단하기 위한 메소드

public class Main {
    public static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Tree tree = new Tree();

        //System.out.println("전위 순회 방식으로 정렬한 노드들의 데이터를 입력합니다.");
        while (true) {

            String data = bufferedReader.readLine();
            if (!isNumber(data)) {
                break;
            }
            int intData = Integer.parseInt(data);
            tree.createNode(intData);
        }
        tree.postOrderTraversal(tree.root);

        bufferedReader.close();
    }

    public static boolean isNumber(String str) {
        try {
            int data = Integer.parseInt(str);
            return true;
        } catch (Exception e) {
            return false;
        }
    }
}