[C] 포화이진트리, 완전이진트리 차이는 뭘까?

포화 이진트리와 완전 이진트리를 알고 가기 이전에, 이진트리 개념을 알아야한다.

이진트리는

노드의 유한집합으로서, 공집합이거나 루트와 왼쪽 오른쪽 서브트리 두 개의 분리된 이진트리로 구성된다.

그럼 포화이진트리는 무엇일까?

포화이진트리(Full BT)

이진트리이면서 서브트리까지 모두 빈 곳 없이 꽉찬 트리를 말한다.
노드의 개수는 n = 2^(높이) - 1이다.

완전 이진 트리(Complete BT)

포화 이진 트리와 헷갈릴 수 있지만 다르다.
완전 이진트리는 높이가 h 일 때 레벨 h-1까지는 Full BT이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리이다.
노드의 개수는 2^(h-1)-1 <= n <= 2^h-1이다.