Cooper's devlog

[문제 접근 방법]

이번 문제는 트리 순회 문제입니다.

이 문제는 이진트리로 전위 순회, 중위 순회, 후위 순회를 탐색하는 방식을 확인하고자 하는 문제 입니다.

문제에서 제시한 것을 다시 한 번 정리하면

• 전위 순회 :  루트 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
• 중위 순회  : 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드
• 후위 순회 :  왼쪽 자식 노드 → 오른쪽 자식 노드 →루트 노드  

순으로 탐색을 한다로 문제에서 제시합니다.

문제 풀이 방식은 먼저

(1)트리를 구현하고

(2)전위(preOrder), 중위(inOrder), 후위(postOrder)로 출력하도록 하는

로직을 작성하는 방식으로 로직을 구성하면 되겠습니다.

[전체 코드]

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

public class Main {
    static Map<Character, char[]> tree = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            char[] node = new char[3];

            node[0] = st.nextToken().charAt(0);
            node[1] = st.nextToken().charAt(0);
            node[2] = st.nextToken().charAt(0);

            tree.put(node[0], node);
        }

        preOrder('A');
        sb.append("\n");

        inOrder('A');
        sb.append("\n");

        postOrder('A');
        sb.append("\n");

        System.out.println(sb.toString());

        br.close();
    }

    private static void postOrder(char node) {
        if(node == '.'){
            return ;
        }

        postOrder(tree.get(node)[1]);
        postOrder(tree.get(node)[2]);
        sb.append(node);
    }

    private static void inOrder(char node) {
        if(node == '.'){
            return ;
        }

        inOrder(tree.get(node)[1]);
        sb.append(node);
        inOrder(tree.get(node)[2]);
    }

    private static void preOrder(char node) {
        if(node == '.'){
            return ;
        }

        sb.append(node);
        preOrder(tree.get(node)[1]);
        preOrder(tree.get(node)[2]);
    }


}

[코드 세부 설명]

1. 트리를 구현한다.

static Map<Character, char[]> tree = new HashMap<>();

트리를 노드를 이용해서 구하는 방식이 있지만 이번 문제 풀이에는 HashMap을 이용해서 트리를 구현했습니다.

<Key, Value>를 가지는 HashMap 형태를 통해 트리를 구현한 것을 확인할 수 있습니다.

2. 전위(preOrder)방식 메소드

    private static void preOrder(char node) {
        if(node == '.'){
            return ;
        }

        sb.append(node);
        preOrder(tree.get(node)[1]);
        preOrder(tree.get(node)[2]);
    }

문제에서 제시해 준 것과 같이 루트 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 메소드를 작성해줍니다.

나머지 아래의 코드 또한 문제에서 제시한 그대로 로직을 구현하도록 합니다.

3. 중위 순회(inOrder)방식 메소드

    private static void inOrder(char node) {
        if(node == '.'){
            return ;
        }

        inOrder(tree.get(node)[1]);
        sb.append(node);
        inOrder(tree.get(node)[2]);
    }

• 중위 순회  : 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드

4. 후위(postOrder)방식 메소드

    private static void postOrder(char node) {
        if(node == '.'){
            return ;
        }

        postOrder(tree.get(node)[1]);
        postOrder(tree.get(node)[2]);
        sb.append(node);
    }

• 후위 순회 :  왼쪽 자식 노드 → 오른쪽 자식 노드 →루트 노드  

[결과]

문제는 깔끔하게 정답인 것을 확인할 수 있습니다! 이 문제는 트리를 구현하는 연습용 문제로 사용하면 좋을 것 같고 기본적인 전위, 후위, 중위표현 방식은 기본적인 CS지식이므로 이번 기회를 통해서 숙지하시면 좋을 것 같습니다!