[BOJ] 백준 1991 트리 순회 (Java)

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

1991번: 트리 순회

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

 

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

성공코드

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

public class BOJ1991 {

    static class Node {
        String data;
        Node left, right;

        public Node(String data) {
            this.data = data;
        }
    }
    static class Tree {
        Node root;

        public void CreateSubtree (String rootdata, String leftdata, String rightdata) {
            if (root == null) {

                root = new Node(rootdata);

                if (!leftdata.equals("."))
                    root.left = new Node(leftdata);
                if (!rightdata.equals("."))
                    root.right = new Node(rightdata);
            }
            else {
                SearchSubtree(root, rootdata, leftdata, rightdata);
            }
        }
        public void SearchSubtree(Node root, String rootdata, String leftdata, String rightdata) {
            if (root == null){
                return;
            }
            else if (root.data.equals(rootdata)) {
                if (!leftdata.equals("."))
                    root.left = new Node(leftdata);
                if (!rightdata.equals("."))
                    root.right = new Node(rightdata);
            }
            else {
                SearchSubtree(root.left, rootdata, leftdata, rightdata);
                SearchSubtree(root.right, rootdata, leftdata, rightdata);
            }

        }
        //전위순회
        public void preorder(Node root){
            if (root != null) {
                System.out.print(root.data);
                preorder(root.left);
                preorder(root.right);
            }
        }
        //중위순회
        public void inorder(Node root){
            if (root != null) {
                inorder(root.left);
                System.out.print(root.data);
                inorder(root.right);
            }
        }
        //후위순회
        public void postorder(Node root){
            if (root != null) {
                postorder(root.left);
                postorder(root.right);
                System.out.print(root.data);
            }
        }
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Tree tree = new Tree();

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            s.replaceAll(" ", "");

            StringTokenizer st = new StringTokenizer(s);
            tree.CreateSubtree(st.nextToken(), st.nextToken(), st.nextToken());
        }

        tree.preorder(tree.root);
        System.out.println();
        tree.inorder(tree.root);
        System.out.println();
        tree.postorder(tree.root);

        br.close();
    }
}

 

Point

1. 트리 생성 ( 루트가 null일 때, 루트가 null이 아닐 때 나누어서 생각 ) -> CreateSubtree

2. 기존에 입력받은 트리와 새로 입력받은 트리 연결 -> SearchSubtree

3. 전위, 중위, 후위 순회 코드 작성 시 재귀 사용

 

코드추가

//try catch문을 사용한 SearchSubtree
public void SearchSubtree(Node root, String rootdata, String leftdata, String rightdata) {
            try {
                if (root.data.equals(rootdata)) {
                    if (!leftdata.equals("."))
                        root.left = new Node(leftdata);
                    if (!rightdata.equals("."))
                        root.right = new Node(rightdata);
                }
                else {
                    SearchSubtree(root.left, rootdata, leftdata, rightdata);
                    SearchSubtree(root.right, rootdata, leftdata, rightdata);
                }
            }catch(NullPointerException e) {

            }

        }

 

Review

자료구조를 배우며 트리 순회 코드를 작성해봤지만 트리 입력 방식이 달라지니 트리를 만드는 것부터 헤맸다｡•́︿•̀｡ 첫 시도에서 TreeSet 라이브러리를 사용하려 했지만 실패,,,, 요리조리 생각해봤지만 답이 나오지 않아 다른 사람들의 코드를 참고했다. 처음에는 SearchSubtree에서 (root == null)일 때 return 조건이 왜 필요한지 몰라서 빼고 코드를 작성했는데 root.left, root.right를 차례대로 탐색하면서 NullPointerException이 발생하는 것을 알았다. 트리의 개념은 알고 있었지만 막상 코드를 작성하려니 어렵게 느껴져서 여러 알고리즘 문제를 풀며 개념을 적용하는 연습을 해야할 것 같다!