그림과 같이 연결되어 있는 11개의 여행지를 관광객들이 모두 방문할 수… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

그림과 같이 연결되어 있는 11개의 여행지를 관광객들이 모두 방문할 수 있도록 안내하기 위해 C언어로 구현한 Course() 함수를 다음과 같이 제시하고 있다. 여행지 H를 파라미터로 하여 알고리즘을 호출했을 때, 출력결과의 (가) ～ (라)에 들어갈 내용을 바르게 연결한 것은? (단, 상위 노드 기준으로 n->left는 왼쪽으로 순회하고 n->right는 오른쪽으로 순회한다)
typedef struct node {
    char name;
    struct node *left;
    struct node *right;
} node;

void Course(node *n) {
    if(n != null) {
        Course(n->left);
        Course(n->right);
        printf("%c->", n->name);
    }
}
○ 출력결과
(가) -> □ -> (나) -> □ -> (다) -> □ ->
□ -> □ -> □ -> (라) -> □ ->

(가) H / (나) A / (다) Z / (라) K

(가) H / (나) T / (다) S / (라) K

(가) N / (나) H / (다) U / (라) T

(가) N / (나) T / (다) E / (라) S

Course()는 왼쪽·오른쪽 서브트리를 먼저 처리한 뒤 노드를 출력하는 후위 순회이므로 (가)~(라)는 각각 N, T, E, S이다.
그림의 트리에서 H의 왼쪽 서브트리 F를 먼저 순회하면 N → U → T → A → E → F 순으로 출력되고, 이어서 오른쪽 서브트리에서 Z → Y → K → S, 마지막으로 H가 출력된다.
전체 출력은 N → U → T → A → E → F → Z → Y → K → S → H이며, (가)는 첫째, (나)는 셋째, (다)는 다섯째, (라)는 열째 값이다.
H·A·Z·K 조합: 루트 H는 후위 순회에서 맨 마지막에 출력되므로 첫째 자리에 올 수 없다.
H·T·S·K 조합: 첫째 자리는 가장 왼쪽 단말 N이며, 열째 자리는 K가 아닌 S이다.
N·H·U·T 조합: H는 마지막에 출력되며, 셋째 자리는 A의 오른쪽 자식 T이다.