문제
아래 트리를 In-Order 방식으로 운행할 경우 올바른 순서는 무엇인가?
<트리 구조>
- 루트 노드는 F이다.
- F의 왼쪽 자식은 A이다.
- A의 왼쪽 자식은 B, 오른쪽 자식은 C이다.
- B의 왼쪽 자식은 D이다.
- C의 왼쪽 자식은 E이다.
- E의 왼쪽 자식은 G, 오른쪽 자식은 H이다.
<조건> 중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문한다.
① A B D C E G H F ② D B A G E H C F ③ D B G H E F C A ④ A B C D E F G H
정답
2번
해설
정답: 2. 중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문한다. 제시된 트리를 중위 순회하면 D → B → A → G → E → H → C → F가 된다.
오답 풀이
- 1번: B의 왼쪽 자식 D를 B보다 먼저 방문하지 않았다.
- 2번: 주어진 트리의 중위 순회 결과이다.
- 3번: A와 F의 방문 위치가 중위 순회와 맞지 않는다.
- 4번: 단순 알파벳 순서에 가깝고 중위 순회 결과가 아니다.
보충 개념 이진 트리의 중위 순회는 Left → Root → Right 순서이다. 서브트리마다 같은 규칙을 재귀적으로 적용한다.