비어 있는 이진 탐색 트리(binary search tree)에 키 값… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
비어 있는 이진 탐색 트리(binary search tree)에 키 값 <7, 5, 1, 8, 3, 6, 0, 9, 4, 2>를 순서대로 삽입한 후, 중위 순회(in-order traversal)한 결과는?
1
0 1 2 3 4 5 6 7 8 9
2
0 2 4 3 1 6 5 9 8 7
3
7 5 1 0 3 2 4 6 8 9
4
9 8 6 4 2 3 0 1 5 7
해설
이진 탐색 트리를 중위 순회하면 키가 오름차순으로 나오므로 결과는 0 1 2 3 4 5 6 7 8 9이다.
BST는 모든 노드에서 왼쪽 서브트리 < 루트 < 오른쪽 서브트리가 성립하고, 중위 순회는 왼쪽 → 루트 → 오른쪽 순으로 방문하므로 삽입 순서와 관계없이 정렬된 순서가 된다.
- 0 2 4 3 1 6 5 9 8 7은 같은 트리를 후위 순회한 결과이다.
- 7 5 1 0 3 2 4 6 8 9는 같은 트리를 전위 순회한 결과이다.
- 9 8 6 4 2 3 0 1 5 7은 오른쪽 서브트리를 먼저 방문하는 후위 순회(오른쪽 → 왼쪽 → 루트) 결과로, 중위 순회와 무관하다.
오류나 개정된 내용이 보이면 알려주세요