[Baekjoon] 1991번: 트리 순회

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

1991번: 트리 순회

문제 설명

주어진 이진 트리를 전위, 중위, 후위 순회한 결과를 출력하면 된다. 별다르게 어려울 건 없다. 이진 트리와 순회 방식만 알면 쉽게 풀 수 있다.

 

이진 트리의 순회는 다음 방식과 같다.

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

풀이 방법

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

class Main {
    
    static class Node {
        char name;
        Node left;
        Node right;
        
        public Node(char name) {
            this.name = name;
        }
    }
    
    static Node[] tree;
    
    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];
        
        for (int i = 0; i < N; i++) {
            tree[i] = new Node((char)('A' + i));
        }
        
        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            char parent = chars[0];
            char left = chars[2];
            char right = chars[4];
            
            if (left != '.') {
                tree[parent - 'A'].left = tree[left - 'A'];
            }
            
            if (right != '.') {
                tree[parent - 'A'].right = tree[right - 'A'];
            }
        }
        
        traversalPreorder(tree[0]);
        System.out.println();
        
        traversalInorder(tree[0]);
        System.out.println();
        
        traversalPostorder(tree[0]);
        System.out.println();
    }
    
    private static void traversalPreorder(Node node) {
        if (node != null) {
            System.out.print(node.name);   
            traversalPreorder(node.left);
            traversalPreorder(node.right);    
        }
    }
    
    private static void traversalInorder(Node node) {
        if (node != null) {
            traversalInorder(node.left);    
            System.out.print(node.name);
            traversalInorder(node.right);    
        }
    }
    
    private static void traversalPostorder(Node node) {
        if (node != null) {
            traversalPostorder(node.left);
            traversalPostorder(node.right);
            System.out.print(node.name);
        }
    }
}