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

이진 트리 자료구조와 재귀 알고리즘 문제에 대한 문제이다.

 

문제 링크 : https://www.acmicpc.net/problem/1991

 

---

문제

 

 

 

참고

참고로 전위 순회, 중위 순회, 후위 순회에 대한 정리가 먼저 필요하다면 아래 게시글을 참고하면 된다.

 

[자료구조] Tree 순회 방법 - 전위/중위/후위 순회 & Java 예시 코드

 

사실 전위/중위/후위 순회를 예시 코드를 통해 이해했다면 이 문제를 푸는 데에도 오랜 시간이 걸리지는 않을 것이다.

 

 

풀이

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));
        int N = Integer.parseInt(br.readLine());
        tree = new Node[N + 1]; // 노드 배열 생성

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 띄어쓰기 기준으로 문자열 분리
            char parentValue = st.nextToken().charAt(0); // nextToken() 메서드로 토큰을 하나씩 꺼내오면 StringTokenizer객체에는 해당 토큰이 사라진다
            char leftValue = st.nextToken().charAt(0);
            char rightValue = st.nextToken().charAt(0);
            
            // Java에서 char 데이터 타입은 내부적으로 ASCII 코드를 사용
            if (tree[parentValue - 'A'] == null) { // 부모 노드가 아직 생성되지 않은 경우. 'A'는 문자 'A'의 ASCII 값
                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();
    }
}