N개의 노드를 가진 완전 이진 트리(complete binary tre… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
N개의 노드를 가진 완전 이진 트리(complete binary tree)에 대한 설명으로 옳지 않은 것은? (단, 루트 노드의 높이는 1로 한다)
1
단말(terminal) 노드의 개수는 비단말(non-terminal) 노드의 개수와 같거나 하나가 더 많다.
2
높이가 K라면 노드 개수 N의 범위는 이다.3
포화 이진 트리(full binary tree)는 완전 이진 트리의 일종이다.
4
완전 이진 트리를 최악으로 구성할 경우 높이는 N이다.
해설
완전 이진 트리는 왼쪽부터 빈틈없이 채우므로 높이가 로 제한되며, 높이가 N이 된다는 설명이 옳지 않다.
높이가 N이 되는 경우는 노드가 한쪽으로만 이어진 편향 이진 트리로, 완전 이진 트리가 될 수 없다.
- 완전 이진 트리의 단말 노드 수는 N/2의 올림, 비단말 노드 수는 내림이므로 같거나 하나 더 많다.
- 높이 K일 때 최소는 마지막 레벨에 노드가 하나인 경우, 최대는 모든 레벨이 꽉 찬 경우이므로 제시된 범위가 성립한다.
- 포화 이진 트리는 모든 레벨이 꽉 찬 트리로 완전 이진 트리의 조건을 만족한다.
오류나 개정된 내용이 보이면 알려주세요