[트리] 백준 1991 트리 순회

1991번: 트리 순회

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

 

# 코드

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

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

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

public class Main {
    static Node[] tree;

    // 전위 순회
    public static void preorder(Node node) {
        if (node == null) return;
        System.out.print(node.value);
        preorder(node.left);
        preorder(node.right);
    }

    // 중위 순회
    public static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value);
        inorder(node.right);
    }

    // 후위 순회
    public static void postorder(Node node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value);
    }

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

        // 노드의 개수 n
        int n = Integer.parseInt(br.readLine());

        // 노드 배열 생성
        tree = new Node[n + 1];

        // n번 반복
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            char parentValue = st.nextToken().charAt(0);
            char leftValue = st.nextToken().charAt(0);
            char rightValue = st.nextToken().charAt(0);

            // 부모 노드가 아직 생성되지 않은 경우
            if (tree[parentValue - 'A'] == null) {
                // 부모 노드를 생성
                tree[parentValue - 'A'] = new Node(parentValue);
            }

            // 왼쪽 자식이 존재할 경우
            if (leftValue != '.') {
                // 왼쪽 자식 노드를 생성하고, 부모 노드와 연결
                tree[leftValue - 'A'] = new Node(leftValue);
                tree[parentValue - 'A'].left = tree[leftValue - 'A'];
            }

            // 오른쪽 자식이 존재할 경우
            if (rightValue != '.') {
                // 오른쪽 자식 노드를 생성하고, 부모 노드와 연결
                tree[rightValue - 'A'] = new Node(rightValue);
                tree[parentValue - 'A'].right = tree[rightValue - 'A'];
            }
        }

        // 전위 순회
        preorder(tree[0]);
        System.out.println();

        // 중위 순회
        inorder(tree[0]);
        System.out.println();

        // 후위 순회
        postorder(tree[0]);
        System.out.println();

        br.close();
    }
}

 

코드와 주석은 아래 블로그를 참고했다.

[백준] 1991 트리 순회 Java 풀이