1991

1. 트리 순회

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

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

가 된다.

2. 나만의 문제 해결

1. 깊이 우선 탐색과 백트래킹을 통해 만들 수 있음.
2. System.out.print((char)(start+'A'));위치만 조정

---

3. code

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int n;
    public static int[] binaryTree;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        binaryTree = new int[2*n];

        for (int i = 0; i < n; i++) {
            char tmp1 = scanner.next().charAt(0);
            for (int j = 0; j < 2 ; j++) {
                char tmp2 = scanner.next().charAt(0);
                if ((int)tmp2 == '.'){
                    binaryTree[(tmp1-'A')*2+j] = -1;
                }
                else{
                    binaryTree[(tmp1-'A')*2+j] = (int)tmp2 - 'A';
                }
            }
        }

        preorderTraversal(0);
        System.out.println();
        inorderTraversal(0);
        System.out.println();
        postorderTraversal(0);
    }
    public static void preorderTraversal(int start){
        System.out.print((char)(start+'A'));
        if (binaryTree[start*2] != -1) {
            preorderTraversal(binaryTree[start*2]);
        }
        if (binaryTree[start*2+1] != -1){
            preorderTraversal(binaryTree[start*2+1]);
        }
    }

    public static void inorderTraversal(int start){
        if (binaryTree[start*2] != -1) {
            inorderTraversal(binaryTree[start*2]);
        }
        System.out.print((char)(start+'A'));
        if (binaryTree[start*2+1] != -1){
            inorderTraversal(binaryTree[start*2+1]);
        }
    }

    public static void postorderTraversal(int start){
        if (binaryTree[start*2] != -1) {
            postorderTraversal(binaryTree[start*2]);
        }
        if (binaryTree[start*2+1] != -1){
            postorderTraversal(binaryTree[start*2+1]);
        }
        System.out.print((char)(start+'A'));
    }
}