[BOJ] 1991 트리 순회 - Java

[문제]

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

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

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

가 된다.

[문제 풀이]

배열과 해쉬맵 두가지 방법으로 입력을 받아서 문제를 해결하였다.

먼저 입력 받은 N 크기 만큼 노드를 만들었다.

노드가 왼쪽, 오른쪽 자식이 있다면 아래 코드와 같이 넣어주었다.

루트부터 시작해서 전위, 중위, 후위 순위를 아래  코드와 같이 돌려주었다.

 

[코드 - 배열]

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

public class Main {

    static int N;
    static Node[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new Node[N];
        for (int i=0; i<N; i++) {
            arr[i] = new Node((char)(i + 'A'));
        }

        for (int i=0; i<N; i++) {
            char n, l, r;
            String s = br.readLine();
            n = s.charAt(0);
            l = s.charAt(2);
            r = s.charAt(4);
            if (l != '.') {
                arr[n-'A'].left = arr[l-'A'];
            }
            if (r != '.'){
                arr[n-'A'].right = arr[r-'A'];
            }
        }

        // 전위 순회
        preOrder(arr[0]);
        sb.append("\n");
        // 중위 순회
        inOrder(arr[0]);
        sb.append("\n");
        // 후위 순회
        postOrder(arr[0]);
        sb.append("\n");

        System.out.println(sb);
    }

    static void preOrder(Node node) {
        sb.append(node.ch);
        if (node.left != null) preOrder(node.left);
        if (node.right != null) preOrder(node.right);
    }

    static void inOrder(Node node) {
        if (node.left != null) inOrder(node.left);
        sb.append(node.ch);
        if (node.right != null) inOrder(node.right);
    }

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.ch);
    }

    static class Node {
        char ch;
        Node left;
        Node right;

        public Node(char ch) {
            this.ch = ch;
        }
    }
}

 

[코드 - 해쉬 맵]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static int N;
    static Map<Character, Node> map = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            map.put((char)('A'+i), new Node((char)('A'+i)));
        }

        for (int i=0; i<N; i++) {
            char n, l, r;
            String s = br.readLine();
            n = s.charAt(0);
            l = s.charAt(2);
            r = s.charAt(4);
            if (l != '.') {
                map.get(n).left = map.get(l);
            }
            if (r != '.'){
                map.get(n).right = map.get(r);
            }
        }

        // 전위 순회
        preOrder(map.get('A'));
        sb.append("\n");
        // 중위 순회
        inOrder(map.get('A'));
        sb.append("\n");
        // 후위 순회
        postOrder(map.get('A'));
        sb.append("\n");

        System.out.println(sb);
    }

    static void preOrder(Node node) {
        sb.append(node.ch);
        if (node.left != null) preOrder(node.left);
        if (node.right != null) preOrder(node.right);
    }

    static void inOrder(Node node) {
        if (node.left != null) inOrder(node.left);
        sb.append(node.ch);
        if (node.right != null) inOrder(node.right);
    }

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.ch);
    }

    static class Node {
        char ch;
        Node left;
        Node right;

        public Node(char ch) {
            this.ch = ch;
        }
    }
}

[실행 결과 - 배열]

[실행 결과 - 해쉬 맵]

실행 결과는 위와 같다.