포화 이진 트리(full binary tree)란 높이가 h일 때 노드 개수가 2h-1인 트리입니다. 모든 레벨에 가능한 모든 노드가 있지요. 그림 7-2가 포화 이진 트리입니다. 완전 이진 트리(complete binary tree)란 높이가 h일 때 레벨 h-1까지 노드 개수는 2h-1-1이고 레벨 h에서는 노드가 왼쪽에서 오른쪽으로 채워지는 트리입니다.
그림 7-4를 보면 높이가 3일 때 레벨 2까지는 모든 가능한 노드가 있고 레벨 3에서는 노드가 왼쪽에서 오른쪽으로 채워져 있는 것을 알 수 있습니다. 이 트리가 계속 완전 이진 트리가 되려면 다음에 추가될 노드는 반드시 3의 왼쪽 자식이어야 합니다.
▲ 그림 7-4 완전 이진 트리
편향 이진 트리(skewed binary tree)는 왼쪽이나 오른쪽 서브 트리만 가진 트리를 의미합니다. 그림 7-3이 편향 이진 트리입니다.