[백준] 1991번 - 트리 순회 (Silver 1)

문제 링크

백준 1991번 - 트리 순회 (Silver 1)

문제 설명

이진 트리의 각 노드와 그 왼쪽 자식, 오른쪽 자식이 주어져 있다.
주어진 자료를 바탕으로 이진 트리를 전위 순회, 중위 순회, 후위 순회 한 결과를 출력한다.

정답 코드 및 설명

binaryTree라는 2차원 배열을 선언하여 왼쪽 자식과 오른쪽 자식을 저장했다.
그 후 전위 순회, 중위 순회, 후위 순회를 시행하여 결과를 출력했다.
이 문제는 노드가 대문자 알파벳 순으로 주어져서 가능했지만, 정석적인 형태는 아니다.

문제에 나온 김에 각 순회 방식을 정리해보면 아래와 같다.

• 전위 순회(preorder) : 부모 노드 - 왼쪽 자식 - 오른쪽 자식 순으로 방문
• 중위 순회(inorder) : 왼쪽 자식 - 부모 노드 - 오른쪽 자식 순으로 방문
• 후위 순회(postorder) : 왼쪽 자식 - 오른쪽 자식 - 부모 노드 순으로 방문

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

public class Main {

    static int[][] binaryTree;
    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));

        int n = Integer.parseInt(br.readLine());
        binaryTree = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node = st.nextToken().charAt(0) - 'A';
            binaryTree[node][0] = st.nextToken().charAt(0) - 'A';
            binaryTree[node][1] = st.nextToken().charAt(0) - 'A';
        }
        preorder(0);
        sb.append('\n');
        inorder(0);
        sb.append('\n');
        postorder(0);
        bw.write(sb.toString());
        bw.close();
    }

    static void preorder(int start) {
        sb.append((char) (start + 'A'));
        if (binaryTree[start][0] != '.' - 'A')
            preorder(binaryTree[start][0]);
        if (binaryTree[start][1] != '.' - 'A')
            preorder(binaryTree[start][1]);
    }

    static void inorder(int start) {
        if (binaryTree[start][0] != '.' - 'A')
            inorder(binaryTree[start][0]);
        sb.append((char) (start + 'A'));
        if (binaryTree[start][1] != '.' - 'A')
            inorder(binaryTree[start][1]);
    }

    static void postorder(int start) {
        if (binaryTree[start][0] != '.' - 'A')
            postorder(binaryTree[start][0]);
        if (binaryTree[start][1] != '.' - 'A')
            postorder(binaryTree[start][1]);
        sb.append((char) (start + 'A'));
    }
}