백준 - 1991 트리 순회(Java)

 

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

1991번: 트리 순회

 

전위, 중위, 후위 탐색문제입니다.

다양한 자료 구조를 사용해서 풀어도 되지만, 저의 경우 Map을 이용해 문제를 풀었습니다.

 

기본적으로 위 세 개의 탐색은 재귀를 이용하면 됩니다. 

단, 정답 출력 부분을 어디에 둘 것인 가에 따라 다른 탐색이 됩니다.

 

이진 트리로 입력을 받기 때문에, 위 세 가지의 탐색 모두 평균 시간복잡도는 O(logV)가 될 것입니다.

경우에 따라 노드가 한 쪽으로만 쏠리는 경우가 있기 때문에, 최악 시간복잡도는 O(V)입니다.

즉, 트리의 시간복잡도는 트리의 높이에 따라 달라집니다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {
    private static int n;
    private static Map<Character, char[]> tree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        tree = new HashMap<>();

        // A부터 맵에 추가함
        for(int i=0; i<n; i++){
            tree.put((char)((int)'A'+i), null);
        }

        for(int i=0; i<n; i++){
            stz = new StringTokenizer(br.readLine());
            char root = stz.nextToken().toCharArray()[0];
            char left = stz.nextToken().toCharArray()[0];
            char right = stz.nextToken().toCharArray()[0];

            tree.put(root, new char[]{left, right});
        }

        preOrder('A', bw);
        bw.write("\n");
        inOrder('A', bw);
        bw.write("\n");
        postOrder('A', bw);

        bw.flush();
        bw.close();
        br.close();
    }

    private static void preOrder(char root, BufferedWriter bw) throws IOException {
        if(root == '.') return;

        bw.write(root);
        preOrder(tree.get(root)[0], bw);
        preOrder(tree.get(root)[1], bw);
    }

    private static void inOrder(char root, BufferedWriter bw) throws IOException {
        if(root == '.') return;

        inOrder(tree.get(root)[0], bw);
        bw.write(root);
        inOrder(tree.get(root)[1], bw);
    }

    private static void postOrder(char root, BufferedWriter bw) throws IOException {
        if(root == '.') return;

        postOrder(tree.get(root)[0], bw);
        postOrder(tree.get(root)[1], bw);
        bw.write(root);
    }
}