[JAVA] 백준 (실버1) 1991번 트리 순회

링크

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

---

문제 설명

정답률 66.952%
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

---

입력 예제

• 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.
• 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.
• 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.
• 자식 노드가 없는 경우에는 .으로 표현한다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

---

출력 예제

• 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다.
• 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

ABDCEFG
DBAECFG
DBEGFCA

---

풀이

이진 트리는 각 노드의 자식 노드의 개수가 2개 이하로 구성돼 있는 트리를 말한다. 트리를 자료구조로 나타낼 때 직관적이면서 편리한 형태는 배열이다. 이진 트리는 다음과 같이 1차원 배열로 표현할 수 있다.

트리의 노드와 배열의 인덱스의 상관 관계는 다음과 같다.

• 루트 노드: index = 1
• 부모 노드: index /= 2 (현재 노드가 루트 노드가 아닐 때)
• 왼쪽 자식 노드: index = 2 (index 2 <= 노드 개수)
• 오른쪽 자식 노드: index = index 2 + 1 (index 2 + 1 <= 노드 개수)

그리고 순회는 다음과 같이 구분된다.

• 전위 순회: 루트 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식
• 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트

이제 예제를 2차원 배열을 이용하여 트리 형태의 자료구조로 저장한다. 알파벳을 int 타입으로 저장하기 위해 char 타입으로 저장한 뒤 'A'를 빼준다.

for (int i = 0; i < N; i++) {
    String[] split = br.readLine().split(" ");
    int parent = split[0].charAt(0) - 'A';
    char left = split[1].charAt(0);
    char right = split[2].charAt(0);
    
    if (left == '.') {
        binaryTree[parent][0] = -1;
    } else {
        binaryTree[parent][0] = left - 'A';
    }
    if (right == '.') {
        binaryTree[parent][1] = -1;
    } else {
        binaryTree[parent][1] = right - 'A';
    }
}

이제 각 순회를 구현한다. 재귀를 이용하며 호출 순서만 다르고 거의 비슷하다.

static void preorder(int node) {
    if (node == -1) {
        return;
    }
    System.out.print((char) (node + 'A'));  //현재 노드
    preorder(binaryTree[node][0]);  //왼쪽 탐색
    preorder(binaryTree[node][1]);  //오른쪽 탐색
}

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.StringTokenizer;

//백준
public class Main {

    static int[][] binaryTree;

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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());  //노드의 개수
        binaryTree = new int[26][2];

        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            int parent = split[0].charAt(0) - 'A';
            char left = split[1].charAt(0);
            char right = split[2].charAt(0);

            if (left == '.') {
                binaryTree[parent][0] = -1;
            } else {
                binaryTree[parent][0] = left - 'A';
            }
            if (right == '.') {
                binaryTree[parent][1] = -1;
            } else {
                binaryTree[parent][1] = right - 'A';
            }
        }
        preorder(0);
        System.out.println();
        inorder(0);
        System.out.println();
        postorder(0);
    }

    static void preorder(int node) {
        if (node == -1) {
            return;
        }
        System.out.print((char) (node + 'A'));  //현재 노드
        preorder(binaryTree[node][0]);  //왼쪽 탐색
        preorder(binaryTree[node][1]);  //오른쪽 탐색
    }

    static void inorder(int node) {
        if (node == -1) {
            return;
        }
        inorder(binaryTree[node][0]);  //왼쪽 탐색
        System.out.print((char) (node + 'A'));  //현재 노드
        inorder(binaryTree[node][1]);  //오른쪽 탐색
    }

    static void postorder(int node) {
        if (node == -1) {
            return;
        }
        postorder(binaryTree[node][0]);  //왼쪽 탐색
        postorder(binaryTree[node][1]);  //오른쪽 탐색
        System.out.print((char) (node + 'A'));  //현재 노드
    }
}