[백준] 1991 트리 순회 - Graph Theory / Java

• 문제 링크

1991번: 트리 순회

 

• 풀이 과정

위와 같은 Tree Graph 가 주어졌을 때

전위 순회(Preorder) 는 루트, 왼쪽, 오른쪽 순으로 탐색, 결과는 A B D H I E J C F G K,

중위 순회(Inorder) 는 왼쪽, 루트, 오른쪽 순으로 탐색, 결과는 H D I B J E A F C K G,

후위 순회(Postorder) 왼쪽, 오른쪽, 루트 순으로 탐색, 결과는 H I D J E B F K G C A 를 나타내며,

이를 바탕으로 각각의 순회 방식을 메소드로 구현한다.

 

Map 객체의 key 값을 기준으로 value 값으로써 왼쪽, 오른쪽 노드를 List 에 저장하여 트리 구조를 구현한다.

 

이 후 재귀 호출을 통해 노드 간 탐색을 수행하고,

StringBuilder 에 이동한 노드를 더하는 시점에 따라 전위, 중위, 후위 순회를 구현한다.

 

이렇게 각각의 순회 방식에 따른 탐색한 노드가 저장된 StringBuilder 객체를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static Map<String, List<String>> tree = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    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 st;

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String root = st.nextToken();

            List<String> node = new ArrayList<>();
            node.add(st.nextToken());
            node.add(st.nextToken());

            tree.put(root, node);
        }

        preorder("A");
        sb.append("\n");

        inorder("A");
        sb.append("\n");

        postorder("A");

        bw.write(sb.toString());
        bw.flush();
    }

    private static void preorder(String node) {
        if (node.equals("."))
            return;

        sb.append(node);
        preorder(tree.get(node).get(0));
        preorder(tree.get(node).get(1));
    }

    private static void inorder(String node) {
        if (node.equals("."))
            return;

        inorder(tree.get(node).get(0));
        sb.append(node);
        inorder(tree.get(node).get(1));
    }

    private static void postorder(String node) {
        if (node.equals("."))
            return;

        postorder(tree.get(node).get(0));
        postorder(tree.get(node).get(1));
        sb.append(node);
    }

}