[필수 문제] 트리 순회 결과 출력하기

1. 문제

루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다.

출력

첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다.

예제 입력

6
0 1 2
1 3 4
2 -1 5
3 -1 -1
4 -1 -1
5 -1 -1

예제 출력

0 1 3 4 2 5
3 1 4 0 2 5
3 4 1 5 2 0

 

 

 

2. 풀이

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int[][] tree;
    
    public static void main(String[] args) throws IOException {

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

        tree = new int[n][2];
        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            tree[a][0] = b;
            tree[a][1] = c;
        }

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

        br.close();
    }

    private static void preOrder(int root) { // 전위 (root, left, right)
        if(tree[root][0] == -1 && tree[root][1] == -1) System.out.print(root + " ");
        else {
            System.out.print(root + " ");
            if(tree[root][0] != -1) preOrder(tree[root][0]);
            if(tree[root][1] != -1) preOrder(tree[root][1]);
        }
    }

    private static void inOrder(int root) { // 중위 (left, root, right)
        if(tree[root][0] == -1 && tree[root][1] == -1) System.out.print(root + " ");
        else {
            if(tree[root][0] != -1) inOrder(tree[root][0]);
            System.out.print(root + " ");
            if(tree[root][1] != -1) inOrder(tree[root][1]);
        }
    }

    private static void postOrder(int root) { // 후위 (left, right, root)
        if(tree[root][0] == -1 && tree[root][1] == -1) System.out.print(root + " ");
        else {
            if(tree[root][0] != -1) postOrder(tree[root][0]);
            if(tree[root][1] != -1) postOrder(tree[root][1]);
            System.out.print(root + " ");
        }
    }

}