Binary Tree

이진 트리는 형태에 따라 크게 세가지로 분류할 수 있습니다.

1. 포화 이진 트리 (full binary tree)
2. 완전 이진 트리 (complete binary tree)
3. 기타 이진 트리

이미지 출처: https://limkydev.tistory.com/134

포화 이진트리

포화 이진 트리, 즉 full binary tree는 말 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 뜻합니다.
만약 높이가 k 인 포화이진 트리가 있다고 해봅시다. 그때, 포화이진 트리는 몇개의 노드를 가지고 있을까요?
모든 레벨에 노드가 꽉 차있으므로 당연히 $2^k-1$개의 노드를 갖게 됩니다.

완전 이진트리

완전 이진 트리는 높이가 k일때, 레벨 1 즉 root 노드부터 k-1까지는 노드가 모두 채워져 있고, 마지막 k 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리입니다.

따라서 왼쪽 그림은 완전 이진트리가 될 수 없습니다.

정리하면, 포화이진트리는 항상 완전 이진트리이지만 그 역은 항상 성립할수는 없습니다.