다음 이진 트리(binary tree)를 <보기>에서 제시한… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
다음 이진 트리(binary tree)를 <보기>에서 제시한 방법을 사용하여 1차원 배열로 표현할 때, 필요한 배열의 최소 크기는? (단, 배열의 인덱스(index)는 0부터 시작하며 배열의 크기는 배열 원소의 개수이다)<보 기>
○ 루트 노드는 배열의 인덱스가 1인 위치에 저장된다.
○ 배열 인덱스가 인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 인 위치에 있으며 오른쪽 자식 노드는 인덱스가 인 위치에 있다.
1
17
2
18
3
34
4
35
해설
가장 큰 인덱스가 34이고 인덱스가 0부터 시작하므로 필요한 배열의 최소 크기는 35이다.
루트 A가 1이면 B는 2, C는 3, D는 , E는 C의 왼쪽 자식이므로 이다.
F는 D의 왼쪽 자식으로 8, G는 F의 오른쪽 자식으로 , H는 G의 왼쪽 자식으로 가 된다. 사용하지 않는 인덱스 0 자리를 포함해 0~34까지 칸이 있어야 한다.
- 17: G의 인덱스 값일 뿐이며 H의 위치 34를 담지 못한다.
- 18: G(인덱스 17)까지만 담는 크기로 H의 위치 34를 담지 못한다.
- 34: 최대 인덱스 34를 담으려면 인덱스 0을 포함해 원소가 35개 필요하므로 하나 부족하다.
오류나 개정된 내용이 보이면 알려주세요
