포화이진트리
-
[자료구조] 완전 이진 트리를 배열로 만들 경우 크기 계산IT 발자취.../알고리즘 2019. 8. 3. 15:16
완전 이진 트리를 동적 배열로 생성하려면 전체 크기 (배열사이즈)를 알아야 합니다. N=5 일 때, 트리의 전체 크기 구하기 완전 이진 트리는 자식이 생길때 마다 노드가 2개씩 증가하는 것을 알 수 있습니다. 완전 이진 트리에서 N = 5 라고 하는 말은 리프 노드의 갯수가 위의 그림과 같이 5개가 있다는 것을 알 수 있습니다. 먼저 트리의 전체 크기를 구하려면 트리의 높이(h)를 먼저 구해야 합니다. 완전 이진 트리의 특성상, ( h >= 1) , 2^(h-1) < N