백준 - 트리 순회 1991번 문제 / DFS풀이

전위 순회, 중위 순회, 후위 순회란 무엇인가?

전위 순회

루트 노드가 가장 먼저 나오는 순회 방식
Root -> Left -> Right
자기 자신 -> 왼쪽 자식을 방문 -> 오른쪽 자식을 방문

중위 순회

각 루트 노드가 자식 노드의 사이에 위치
Left -> Root -> Right
왼쪽 자식을 방문 -> 자기 자신 -> 오른쪽 자식을 방문

후위 순회

루트 노드가 가장 마지막에 출력
Left -> Right -> Root
왼쪽 자식을 방문 -> 오른쪽 자식을 방문 -> 자기 자신

접근 방법

DFS를 이용한 구현
왼쪽, 오른쪽을 구분할 수 있는 2차원 배열 생성
배열 안에 값을 알파벳 말고 숫자로 담은 후 출력만 알파벳으로!

구현

전위 순회:

DFS를 시작했을 때, 그 값을 먼저 출력하고 계속 파고드는 방식

중위 순회:

DFS시작하고 왼쪽 끝까지 들어간 후, 더이상 값이 존재하지 않을 때 출력하면서 오른쪽 접근

후위 순회:

왼쪽, 오른쪽 다 방문하면서 마지막에 루트를 출력하는 방식

코드

package 트리.실버.트리순회_1991;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class ReMain {
    public static int n;
    public static int[][] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int location = st.nextToken().charAt(0) - 'A';
            int a = st.nextToken().charAt(0) - 'A';
            int b = st.nextToken().charAt(0) - 'A';
 
            if (a == -19) {
                arr[location][0] = -1;
            } else {
                arr[location][0] = a;
            }
 
            if (b == -19) {
                arr[location][1] = -1;
            } else {
                arr[location][1] = b;
            }
        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < 2; j++) {
//                System.out.print(arr[i][j] + " ");
//            }
//            System.out.println();
//        }
        preOrder(0);
        System.out.println();
        inOrder(0);
        System.out.println();
        postOrder(0);
 
 
 
    }
    
    public static void preOrder(int start) {
        if (start == -1) {
            return;
        }
        System.out.print((char) (start + 'A'));
        preOrder(arr[start][0]);
        preOrder(arr[start][1]);
    }
 
    public static void inOrder(int start) {
        if (start == -1) {
            return;
        }
 
        inOrder(arr[start][0]);
        System.out.print((char) (start + 'A'));
        inOrder(arr[start][1]);
    }
 
    public static void postOrder(int start) {
        if (start == -1) {
            return;
        }
 
        postOrder(arr[start][0]);
        postOrder(arr[start][1]);
        System.out.print((char) (start + 'A'));
    }
}