78개의 간선(edge)으로 이루어진 이진 트리(binary tree)… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
78개의 간선(edge)으로 이루어진 이진 트리(binary tree)가 가질 수 있는 최대 높이와 최소 높이의 차이는? (단, 루트 노드만 존재하는 이진 트리의 높이는 1이다)
1
71
2
72
3
73
4
74
해설
최대 높이와 최소 높이의 차이는 72이다.
간선이 78개이면 노드 수는 간선 수+1인 79개이다. 최대 높이는 노드가 한 줄로 이어진 편향 트리일 때로 79이다.
최소 높이는 완전 이진 트리 형태일 때로, 높이 h의 최대 노드 수 이 79 이상이 되는 최소 h를 찾는다.
이므로 최소 높이는 7이다.따라서 차이는 79-7=72이다.
오류나 개정된 내용이 보이면 알려주세요