다음 정수를 왼쪽부터 순서대로 삽입하여 이진 탐색 트리(binary s… | [계리직 컴퓨터일반] 21년 1회차 기출문제 상세 페이지
1[계리직 컴퓨터일반] 21년 1회차
다음 정수를 왼쪽부터 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성했을 때 단말 노드(leaf node)를 모두 나열한 것은?44, 36, 62, 3, 16, 51, 75, 68, 49, 85, 57
1
16, 49, 51, 57, 85
2
16, 49, 57, 68, 85
3
49, 51, 57, 68, 85
4
49, 57, 68, 75, 85
해설
단말 노드는 16, 49, 57, 68, 85이다.
이진 탐색 트리는 루트부터 비교해 작으면 왼쪽, 크면 오른쪽으로 내려가 빈 자리에 삽입한다.
루트 44의 왼쪽에 36, 36의 왼쪽에 3, 3의 오른쪽에 16이 붙는다. 오른쪽은 62 아래 왼쪽 51(자식 49·57), 오른쪽 75(자식 68·85)가 된다. 자식이 없는 노드는 16, 49, 57, 68, 85이다.
- 16, 49, 51, 57, 85: 51은 49와 57을 자식으로 가지는 내부 노드이고, 단말 노드인 68이 빠졌다.
- 49, 51, 57, 68, 85: 3의 오른쪽 자식인 16이 단말 노드인데 빠졌고, 내부 노드인 51이 들어갔다.
- 49, 57, 68, 75, 85: 75는 68과 85를 자식으로 가지는 내부 노드이고, 단말 노드인 16이 빠졌다.
오류나 개정된 내용이 보이면 알려주세요