키 값이 1, 2, 3, 4, 5, 6, 7, 8인 8개의 노드로 구성… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
키 값이 1, 2, 3, 4, 5, 6, 7, 8인 8개의 노드로 구성된 이진 탐색 트리를 전위 순회(preorder traversal)하면, 키 값 6, 2, 1, 4, 3, 5, 8, 7 순서로 노드를 방문한다. 이 트리를 후위 순회(postorder traversal)할 경우 방문 노드의 키 값을 방문 순서대로 바르게 나열한 것은?
1
1, 2, 3, 4, 5, 6, 7, 8
2
1, 3, 2, 6, 5, 8, 7, 4
3
1, 3, 5, 4, 2, 7, 8, 6
4
8, 7, 6, 5, 4, 3, 2, 1
해설
후위 순회 결과는 1, 3, 5, 4, 2, 7, 8, 6이다.
전위 순회의 첫 키 6이 루트이고, 이진 탐색 트리이므로 6보다 작은 2, 1, 4, 3, 5는 왼쪽, 8, 7은 오른쪽 서브트리이다. 같은 방식으로 왼쪽은 2(왼쪽 1, 오른쪽 4(왼쪽 3, 오른쪽 5)), 오른쪽은 8(왼쪽 7)로 복원된다.
후위 순회는 왼쪽 → 오른쪽 → 루트 순이므로 1, 3, 5, 4, 2를 방문한 뒤 7, 8, 마지막에 루트 6을 방문한다.
- 1부터 8까지 오름차순: 이진 탐색 트리의 중위 순회 결과이다.
- 1, 3, 2, 6, 5, 8, 7, 4: 루트 6이 마지막에 오지 않아 후위 순회가 될 수 없다.
- 8부터 1까지 내림차순: 오른쪽 → 루트 → 왼쪽으로 도는 역방향 중위 순회 결과이다.
오류나 개정된 내용이 보이면 알려주세요