백준 1991 트리 순회 Java

solved.ac = 실버 1

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

1991번: 트리 순회

 

1. 접근

 

트리의 개념을 코드로 구현해내는 가장 기본적인 문제가 아닐까 싶다.

자료구조 2번에 트리에 대해서 간단히 정리해두었으니 모르는 분은 한 번 보고 오셔도 될 것 같다!

 

https://dhbang.tistory.com/14?category=905670 

자료구조 - 2

 

전위, 중위, 후위 순회를 하려면 DFS를 재귀적으로 호출했을 때 스택이 어떻게 쌓이는지 흐름을 따라가봐야 한다.

 

아래의 전위 순회 코드를 보며 이해해보자.

static void preOrder(int x) {
    if (x == -1) return;
    // 현재 노드값 출력
    sb.append((char)(x + 'A'));
    // 왼쪽 자식 호출
    preOrder(tree[x][0]);
    // 오른쪽 자식 호출
    preOrder(tree[x][1]);
}

코드 순서에 따라 비어있는 값인 -1이면 함수를 종료시키고 그게 아니라면

출력 - 왼쪽 - 오른쪽 순으로 반복하며 뻗어나가게 되는데 위 함수의 실행되는 순서는 아래와 같다.

왼쪽, 오른쪽으로 뻗어 나가는것은 동일하지만 순회 방법에 따라 출력 부분이 코드상 어디에 위치해야 하는지를 생각하며 풀어보자!

 

2. 풀이

 

변수 세팅

static int N;
static int[][] tree;
public static void main(String[] args) throws IOException {
    N = Integer.parseInt(br.readLine());
    tree = new int[26][2];
    for (int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        // 입력에서 주어지는 대문자 알파벳에서 - A를 빼면 0 ~ 숫자
        int parent = st.nextToken().charAt(0) - 'A';
        int childX = st.nextToken().charAt(0) - 'A';
        int childY = st.nextToken().charAt(0) - 'A';
        // 비어있다는 표시인 .이 주어지면 값은 -19가 나온다.
        tree[parent][0] = (childX == -19) ? -1 : childX;
        tree[parent][1] = (childY == -19) ? -1 : childY;
    }
    solution();
}

 

순회 및 정답 출력

static void solution() {
    // 전위 순회
    preOrder(0);
    sb.append('\n');
    // 중위 순회
    inOrder(0);
    sb.append('\n');
    // 후위 순회
    postOrder(0);
    System.out.println(sb.toString());
}

 

각 순회

// 전위 순회
static void preOrder(int x) {
    if (x == -1) return;
    // 현재 노드값 출력
    sb.append((char)(x + 'A'));
    // 왼쪽 자식 호출
    preOrder(tree[x][0]);
    // 오른쪽 자식 호출
    preOrder(tree[x][1]);
}
// 중위 순회
static void inOrder(int x) {
    if (x == -1) return;
    // 왼쪽 자식 호출
    inOrder(tree[x][0]);
    // 현재 노드값 출력
    sb.append((char)(x + 'A'));
    // 오른쪽 자식 호출
    inOrder(tree[x][1]);
}
// 후위 순회
static void postOrder(int x) {
    if (x == -1) return;
    // 왼쪽 자식 호출
    postOrder(tree[x][0]);
    // 오른쪽 자식 호출
    postOrder(tree[x][1]);
    // 현재 노드값 출력
    sb.append((char)(x + 'A'));
}

 

3. 전체 코드