[1231] 중위순회

✔ 중위순회

[SWEA 1231]

문제 분석하기

주어진 입력값을 트리 형태의 자료구조에 적절하게 저장하고, 그 안에서 탐색을 수행하는 로직을 구현

트리는 완전 이진 트리이므로 무조건 인덱스 * 2, 인덱스 * 2 + 1로 이동하며 아래로 내려감

손으로 풀어보기

1. 1차원 배열에 트리의 알파벳 저장
2. 루트 노드부터 시작하여 노드의 왼쪽 트리, 노드, 노드의 오른쪽 트리를 반복하여 N이 될 때까지 출력
   • 노드의 왼쪽은 루트 노드의 인덱스 * 2
   • 노드의 오른쪽은 루트 노드의 인덱스 * 2 + 1 

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    N(트리가 갖는 정점의 총 수)
    tree(트리의 알파벳 저장)
    for(i -> N만큼) {
        tree[i] = 알파벳만 저장
    }
    #T + 공백 출력
    중위순회(1)
}

중위순회 {
    if(index * 2가 N보다 작거나 같을 때) {
        중위순회(index * 2)
    }
    tree[index] 출력
    if (index * 2 + 1이 N보다 작거나 같을 때) {
        중위순회(index * 2 + 1)
    }
}

코드 구현하기

/**
 * 1231) 중위순회
 */
public class D001_1231 {
    static int N;
    static String[] tree;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // N(트리가 갖는 정점의 총 수)
            N = sc.nextInt();
            sc.nextLine();
            // tree(트리의 알파벳 저장)
            tree = new String[N + 1];
            // 알파벳만 저장
            for (int i = 1; i <= N; i++) {
                String str = sc.nextLine();
                tree[i] = str.split(" ")[1];
            }
            // #T + 공백 출력
            System.out.printf("#%d ", test_case);
            // 중위순회(1)
            inOrder(1);
            System.out.println();
        }
    }

    // 중위순회
    private static void inOrder(int index) {
        // index * 2가 N보다 작거나 같을 때
        if (index * 2 <= N) {
            // 현재 노드의 왼쪽 트리 중위순회
            inOrder(index * 2);
        }
        // 현재 노드인 tree[index] 출력
        System.out.print(tree[index]);
        // index * 2 + 1이 N보다 작거나 같을 때
        if (index * 2 + 1 <= N) {
            // 현재 노드의 오른쪽 트리 중위순회
            inOrder(index * 2 + 1);
        }
    }
}