[백준] 1991번 - 트리 순회 [Java]

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

 

[백준] 1991번 - 트리 순회 [Java]

[백준] 1991번 - 트리 순회 [Java]

---

1.  아이디어

 

트리에 대한 전위 순회, 중위 순회, 후위 순회를 구현하는 문제로 전위 순회는 현재 노드를 방문한 후 왼쪽 자식, 오른쪽 자식 순으로 방문하고, 중위 노드는 왼쪽 자식을 방문 후 현재 노드를 방문하고 오른쪽 자식을 방문하고, 후위 순회는 왼쪽 자식을 방문하고 오른쪽 자식을 방문하고 현재 노드를 방문한다. 이를 재귀적으로 구현하면 해결할 수 있다.

---

2. 문제풀이

 

출력을 위해 전역 StringBuilder를 활용했고 왼쪽 자식의 알파벳, 오른쪽 자식의 알파벳을 갖는 Node 클래스를 활용해서 구현했다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        char leftChild;
        char rightChild;

        public Node(char leftChild, char rightChild) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    private static final StringBuilder sb = new StringBuilder();
    private static final Map<Character, Node> adj = new HashMap<>();

    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());
            char node = st.nextToken().charAt(0);
            char leftChild = st.nextToken().charAt(0);
            char rightChild = st.nextToken().charAt(0);
            adj.put(node, new Node(leftChild, rightChild));
        }

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

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

        postorder('A');

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

    // 전위 순회
    private static void preorder(char node) {
        if (node == '.') return;

        sb.append(node);
        preorder(adj.get(node).leftChild);
        preorder(adj.get(node).rightChild);
    }

    // 중위 순회
    private static void inorder(char node) {
        if (node == '.') return;

        inorder(adj.get(node).leftChild);
        sb.append(node);
        inorder(adj.get(node).rightChild);
    }

    // 후위 순회
    private static void postorder(char node) {
        if (node == '.') return;

        postorder(adj.get(node).leftChild);
        postorder(adj.get(node).rightChild);
        sb.append(node);
    }

}

---

4. 후기