이진 트리에 대한 설명으로 옳은 것만을 모두 고르면?ㄱ. 공백 이진 트… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

이진 트리에 대한 설명으로 옳은 것만을 모두 고르면?
ㄱ. 공백 이진 트리의 높이를 0으로 본다면, 높이가 5인 이진 트리의 최대 노드 수는 15이다.
ㄴ. 9개의 노드를 가지고 있는 이진 트리는 8개의 간선을 가진다.
ㄷ. 루트 노드의 인덱스를 1로 하는 1차원 배열로 완전 이진 트리를 표현할 때, 인덱스 13인 노드의 부모 노드는 인덱스가 7이다.
ㄹ. 7개 노드로 구성할 수 있는 이진 트리의 최대 높이와 최소 높이의 차는 4이다.

ㄱ, ㄴ

ㄴ, ㄷ

ㄴ, ㄹ

ㄷ, ㄹ

옳은 것은 ㄴ, ㄹ이다.
ㄴ: 트리는 노드가 n개이면 간선이 n−1개이므로 9개 노드는 간선 8개다.
ㄹ: 7개 노드의 최대 높이는 한 줄로 늘어선 경우 7, 최소 높이는 완전 이진 트리인 경우 3이므로 차는 4이다.
ㄱ: 높이 5인 이진 트리의 최대 노드 수는 $2^5-1=31$ 이므로 15가 아니다.
ㄷ: 인덱스 i의 부모는 $\lfloor i/2 \rfloor$ 이므로 13의 부모는 6이다.