[BOJ_1991] 트리 순회

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

1991번: 트리 순회

A가 루트인 이진 트리가 주어집니다.

이 트리를 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제입니다.

 

 

💎 트리 표현 방법

1. static class Node를 선언했습니다. 현재 노트의 알파벳 값인 value, 왼쪽, 오른쪽 노드인 left, right를 멤버 변수로 가지고 있습니다.
2. HashMap<Character, Node>를 사용하여 트리에 포함된 노드들을 저장했습니다.
   Key는 Node.value를, value는 Node 객체가 매핑됩니다.

 

💎 순회 방법
모든 순회는 재귀적으로 이루어집니다.

1. 전위순회 (preorder)
   전위 순회는 루트 -> 왼쪽 -> 오른쪽 순으로 트리를 순회합니다.
   (1) 먼저 현재 value를 출력합니다.
   (2) 왼쪽 노드가 있는 경우 왼쪽 노드로 이동합니다.
   (3) 왼쪽 노드를 다녀온 이후, 오른쪽 노드가 있는 경우 오른쪽 노드로 이동합니다.
2. 중위순회 (inorder)
   중위 순회는 왼쪽 -> 루트 -> 오른쪽 순으로 트리를 순회합니다.
   (1) 먼저 왼쪽 노드가 있는 경우 왼쪽 노드로 이동합니다.
   (2) 왼쪽 노드 순회를 마쳤다면 현재 value를 출력합니다.
   (3) 오른쪽 노드가 있는 경우 오른쪽 노드로 이동합니다.
3. 후외순회 (postorder)
   후위 순회는 왼쪽 -> 오른쪽 -> 루트 순으로 트리를 순회합니다.
   (1) 먼저 왼쪽 노드가 있는 경우 왼쪽 노드로 이동합니다.
   (2) 왼쪽 노드 순회를 마쳤다면 오른쪽 노드로 이동합니다.
   (3) 왼쪽, 오른쪽 노드를 모두 다녀왔다면 현재 value를 출력합니다.

💎 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BOJ_1991 {

    static class Node {
        char value;
        Node left;
        Node right;

        Node(char value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "value: " + value + ", left : " + left + ", right : " + right;
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Node> graph = new ArrayList<>();
        HashMap<Character, Node> map = new HashMap<>();

        for (int i=0; i<N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine());

            char parent = stk.nextToken().charAt(0);

            char left = stk.nextToken().charAt(0);
            Node leftNode = map.getOrDefault(left, new Node(left, null, null));
            map.put(left, leftNode);

            char right = stk.nextToken().charAt(0);
            Node rightNode = map.getOrDefault(right, new Node(right, null, null));
            map.put(right, rightNode);

            Node parentNode = map.getOrDefault(parent, new Node(parent, leftNode, rightNode));
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            map.put(parent, parentNode);

            graph.add(new Node(parent, leftNode, rightNode));

        }

        preorder(map.get('A'));
        System.out.print("\n");
        inorder(map.get('A'));
        System.out.print("\n");
        postorder(map.get('A'));
    }

    // 전위순회 (루트 -> 왼쪽 -> 오른쪽)
    private static void preorder(Node current) {
        System.out.print(current.value);

        // 왼쪽
        if (current.left.value != '.')
            preorder(current.left);

        // 오른쪽
        if (current.right.value != '.')
            preorder(current.right);
    }

    // 중위순회 (왼쪽 -> 루트 -> 오른쪽)
    private static void inorder(Node current) {
        // 왼쪽
        if (current.left.value != '.')
            inorder(current.left);

        System.out.print(current.value);

        // 오른쪽
        if (current.right.value != '.')
            inorder(current.right);
    }

    // 후외순회 (왼쪽 -> 오른쪽 -> 루트)
    private static void postorder(Node current) {
        // 왼쪽
        if (current.left.value != '.')
            postorder(current.left);

        // 오른쪽
        if (current.right.value != '.')
            postorder(current.right);

        System.out.print(current.value);
    }
}