[Java] 트리 순회 (Lv. Sliver1)

트리 순회 (Lv. Sliver1)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

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

public class Main {
    static int[][] tree;
    static StringBuilder sb = new StringBuilder();

    public static void preOrder(int start) {
        if (start != -18) {
            sb.append((char) (start + 'A' - 1));
            preOrder(tree[start][0]);
            preOrder(tree[start][1]);
        }
    }

    public static void inOrder(int start) {
        if (start != -18) {
            inOrder(tree[start][0]);
            sb.append((char) (start + 'A' - 1));
            inOrder(tree[start][1]);
        }
    }

    public static void postOrder(int start) {
        if (start != -18) {
            postOrder(tree[start][0]);
            postOrder(tree[start][1]);
            sb.append((char) (start + 'A' - 1));
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tree = new int[n + 1][2];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char a = st.nextToken().charAt(0);
            char b = st.nextToken().charAt(0);
            char c = st.nextToken().charAt(0);

            int parent = a - 'A' + 1;
            int left = (b == '.') ? -18 : b - 'A' + 1;
            int right = (c == '.') ? -18 : c - 'A' + 1;

            tree[parent][0] = left;
            tree[parent][1] = right;
        }

        preOrder(1);
        sb.append("\n");
        inOrder(1);
        sb.append("\n");
        postOrder(1);
        sb.append("\n");

        System.out.print(sb.toString());
    }
}

 

- 'A' + 1 코드는 A~Z를 정수로 변환하는 과정입니다. tree[parent][0] = left; 에 i번 노드의 왼쪽 자식, tree[parent][1] = right; 에 i번 노드의 오른쪽 자식을 저장합니다.

 

if (start != -18) {
    sb.append((char) (start + 'A' - 1));
    preOrder(tree[start][0]);
    preOrder(tree[start][1]);
}

 

sb.append((char) (start + 'A' - 1)); 를 통해 루트를 지정해줍니다. preOrder(tree[start][0]); 에서 start 안에 루트값이 들어가게 되고 트리의 왼쪽 자식부터 재귀적으로 호출됩니다. 그리고 if (start != -18) 조건문을 통해 루트값이 없을 때까지 작동합니다.

루트값을 가장 먼저 정하면 전위순회, 루트값을 중간에 정하면 중위순회, 루트값을 마지막에 정하면 후위순회를 할 수 있습니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3