문제 설명

트리를 주면, 그 트리에 대한 전위, 중위, 후위 순회를 순차적으로 하고 각 결과를 출력하면 된다.

전위순회, 중위순회, 후위순회

아... 너무 오랜만에 본다. 분명 학교 알고리즘 시간에 배운건 기억이 나는데 아리송해서 그냥 개념 정리할겸 유튜브에 있는 5분짜리 영상을 하나봤다.
우선, 기본적인 이진트리 구조를 분할정복을 하듯이 일부분을 캡쳐해보자.
여기서 세가지 선택지가 있다. 이 root(사진에서 2), left(사진에서 4), right(사진에서 5) 중 뭘 먼저 출력할거냐를 반복하는 구조다.

전위 순회

전위 순회는 현재 내가 있는 위치의 노드를 먼저 출력하고 왼쪽노드 방향으로 이동하고 그 다음 오른쪽 노드 방향으로 이동한다는 것임.

중위 순회, 후위 순회

둘 다 전위 순회와 원리는 같다. 그냥 현재 내가 있는 노드를 중간에서 출력하면 중위순회고, 마지막에 출력하면 후위순회다.

코드 구현은 셋 다 너무 단순해서 생략하겠다. 아래 코드에서 preorder, inorder, postorder 함수를 보면 된다.

문제 풀이

여기서 Tree클래스는 사실 없어도 된다. 그냥 트리 구조처럼 보이고 싶어서 추가한 클래스다.

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


public class Main {
    public static class Node {
        final String data;
        Node left = null;
        Node right = null;

        Node(String data) {
            this.data = data;
        }
    }

    public static class Tree {
        final Node root;

        Tree(Node root) {
            this.root = root;
        }
    }

    public static Tree tree;

    public static HashMap<String, Node> map = new HashMap<>();

    static Node getNode(String key) {
        if (map.containsKey(key)) return map.get(key);
        Node newNode = new Node(key);
        map.put(key, newNode);
        return newNode;
    }

    static StringBuilder sb;

    static void preOrder(Node node) {
        if (node != null) {
            sb.append(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    static void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            sb.append(node.data);
            inOrder(node.right);
        }
    }

    static void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            sb.append(node.data);
        }
    }

    public static void main(String[] args) throws IOException {        // 현재 시간을 가져오기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        for (int i = 0; i < size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String key = st.nextToken();
            String leftKey = st.nextToken();
            String rightKey = st.nextToken();
            Node curNode = getNode(key);
            if (!leftKey.equals(".")) curNode.left = getNode(leftKey);
            if (!rightKey.equals(".")) curNode.right = getNode(rightKey);
        }
        tree = new Tree(map.get("A"));

        sb = new StringBuilder();
        preOrder(tree.root);
        System.out.println(sb);

        sb = new StringBuilder();
        inOrder(tree.root);
        System.out.println(sb);

        sb = new StringBuilder();
        postOrder(tree.root);
        System.out.println(sb);
    }
}

배운점
오랜만에 스트링 비교를 해서 찾아보다가 자바에서 대소문자 무시 비교 메소드가 있다는걸 발견했다. 코테에서 유용하게 쓰일 듯 싶다.

참고로 코틀린에서는 대소문자 무시 비교를 하고 싶다면 equals의 두번째 파라미터로 true를 주면 된다고 한다.