깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 09년 1회차
깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A - B의 값은? (단, 루트노드의 레벨은 1로 한다)
1
2
3
4
해설
A − B 의 값은 이다.
최대 노드 수는 모든 레벨이 꽉 찬 포화 이진트리일 때로, 레벨 i에 개씩 있으므로 이다.
최소 노드 수는 레벨마다 노드가 하나뿐인 편향 이진트리일 때로 이다.
- : 깊이 1이면 노드가 하나뿐이라 A − B 는 0이어야 하는데 3이 된다.
- : 깊이 1에서 1이 되어 0이 아니므로 맞지 않는다.
- : 깊이 1에서 2가 되어 상수항 부호가 틀렸다.
오류나 개정된 내용이 보이면 알려주세요