1991번 트리 순회

문제: 트리 순회

• 트리 순회 개념을 안다면 다른 것보다 트리를 어떻게 구현했냐가 중요한 문제인 거 같습니다.
• 저는 2차원 인접행렬을 사용해서 트리를 구현했습니다.
  • 0번 인덱스에는 왼쪽 자식 노드, 1번 인덱스에는 오른쪽 자식 노드
• 트리만 잘 구현하고 트리 순회 순서에 맞게 호출하면 해결할 수 있습니다.

코드

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


public class Main {

    public static int N;
    public static int[][] tree;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        tree = new int[N][2];

        for (int i = 0; i < N; ++i) {
            String[] treeInfo = br.readLine().split(" ");

            int parent = parseToInt(treeInfo[0]);
            int leftChild = parseToInt(treeInfo[1]);
            int rightChild = parseToInt(treeInfo[2]);

            tree[parent][0] = leftChild;
            tree[parent][1] = rightChild;
        }

        preOrder(0);
        System.out.println();
        inOrder(0);
        System.out.println();
        postOrder(0);
        System.out.println();
    }

    public static int parseToInt(String idx) {
        if (idx.equals(".")) {
            return -1;
        }

        return idx.charAt(0) - 'A';
    }

    public static void preOrder(int node) {
        char c = (char)(node + 65);
        System.out.print(c);

        for (int idx = 0; idx < 2; ++idx) {
            if (tree[node][idx] != -1) {
                preOrder(tree[node][idx]);
            }
        }
    }

    public static void inOrder(int node) {
        if (tree[node][0] != -1) {
            inOrder(tree[node][0]);
        }

        char c = (char)(node + 65);
        System.out.print(c);

        if (tree[node][1] != -1) {
            inOrder(tree[node][1]);
        }
    }

    public static void postOrder(int node) {
        for (int idx = 0; idx < 2; ++idx) {
            if (tree[node][idx] != -1) {
                postOrder(tree[node][idx]);
            }
        }

        char c = (char)(node + 65);
        System.out.print(c);
    }
}