1991 - 트리 순회

이 문제는 이진 트리 순회 방법을 연습하는 문제이다. 문제 설명에도 나와있지만, 이진 트리를 순회하는 방법에는 크게 preorder, inorder, postorder 방식이 있다. preorder의 경우는 root-left-right, inorder은 left-root-right, postorder은 left-right-root 순으로 순회하게 된다. 참고로 루트 노드의 순서에 따른 이름으로 외우면 편하다.

문제에서는 A노드가 항상 루트라고 하였으므로 A노드 기준으로 preorder, inorder, postorder traverse를 수행하면 된다.

🔗 문제 링크

코드

먼저 그래프를 저장하기 위해 인접 리스트 형태로 변수를 선언한다.

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Map<String, List<String>> graph = new HashMap<>();
// ...

다음으로 노드 수와 연결 관계(간선)을 입력받아 인접 리스트에 저장한다.

public static void main(String[] args) throws IOException{
    int T = Integer.parseInt(br.readLine());
    for (int i = 0; i < T; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String parent = st.nextToken();
        String child1 = st.nextToken();
        String child2 = st.nextToken();

        graph.put(parent, List.of(child1, child2));
    }
    // ...

마지막으로 루트 노드인 A 기준으로 preorder, inorder, postorder traverse를 시행한다. 이 세 순회 함수들은 모두 재귀적으로 구현되어 있다.

    // ...
    preorder("A");
    bw.write("\n");
    inorder("A");
    bw.write("\n");
    postorder("A");
    bw.write("\n");

    bw.flush();
    bw.close();
}  

먼저 preorder 부터 살펴보자. 앞서 설명했듯이 preorder traverse는 root-left-right 순서로 트리를 순회한다. 따라서 그래프에서 자식 노드를 찾은 뒤, root 노드를 먼저 출력하고, 그 후 childLeft-childRight 순으로 preorder 순회를 다시 실시한다. 만약 childLeft나 childRight가 없는 경우 순회는 일어나지 않으므로 리프 노드에서 순회는 중단될 것이므로 무한 루프 문제는 일어나지 않을 것이다.

public static void preorder(String node) throws IOException {
    List<String> children = graph.get(node);
    String childLeft = children.get(0);
    String childRight = children.get(1);
    bw.write(node);
    if (!childLeft.equals(".")) preorder(childLeft);
    if (!childRight.equals(".")) preorder(childRight);
}

inorder과 postorder의 경우도 전체적인 구조는 같지만 bw.write의 순서가 바뀐 것을 알 수 있다.

public static void inorder(String node) throws IOException {
    List<String> children = graph.get(node);
    String childLeft = children.get(0);
    String childRight = children.get(1);
    if (!childLeft.equals(".")) inorder(childLeft);
    bw.write(node);
    if (!childRight.equals(".")) inorder(childRight);
}

public static void postorder(String node) throws IOException {
    List<String> children = graph.get(node);
    String childLeft = children.get(0);
    String childRight = children.get(1);
    if (!childLeft.equals(".")) postorder(childLeft);
    if (!childRight.equals(".")) postorder(childRight);
    bw.write(node);
}

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Map<String, List<String>> graph = new HashMap<>();

    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String parent = st.nextToken();
            String child1 = st.nextToken();
            String child2 = st.nextToken();

            graph.put(parent, List.of(child1, child2));
        }

        preorder("A");
        bw.write("\n");
        inorder("A");
        bw.write("\n");
        postorder("A");
        bw.write("\n");
    
        bw.flush();
        bw.close();
    }   
    
    public static void preorder(String node) throws IOException {
        List<String> children = graph.get(node);
        String childLeft = children.get(0);
        String childRight = children.get(1);
        bw.write(node);
        if (!childLeft.equals(".")) preorder(childLeft);
        if (!childRight.equals(".")) preorder(childRight);
    }

    public static void inorder(String node) throws IOException {
        List<String> children = graph.get(node);
        String childLeft = children.get(0);
        String childRight = children.get(1);
        if (!childLeft.equals(".")) inorder(childLeft);
        bw.write(node);
        if (!childRight.equals(".")) inorder(childRight);
    }

    public static void postorder(String node) throws IOException {
        List<String> children = graph.get(node);
        String childLeft = children.get(0);
        String childRight = children.get(1);
        if (!childLeft.equals(".")) postorder(childLeft);
        if (!childRight.equals(".")) postorder(childRight);
        bw.write(node);
    }
}

시간 복잡도

트리의 노드 개수는 $N$ 개이고 이를 세 번 순회하므로 시간복잡도는 $O(3N) = O(N)$이다.