그림 7-2에서 트리의 최대 노드 개수는 어떻게 될까요? 레벨이 3일 때고 모든 레벨에 가능한 모든 노드가 존재합니다. 직접 세어 보면 노드가 일곱 개 있군요. 이를 일반화하면 트리 높이가 h일 때 이진 트리에서 가능한 최대 노드 개수는 다음과 같습니다.

2^h-1

레벨이 4라면 15개가 되겠군요. 그렇다면 트리 높이가 h일 때 트리의 최소 노드 개수는 어떻게 구할 수 있을까요? 그림을 봅시다.

▲ 그림 7-3 트리의 최소 노드 개수

그림 7-3은 트리 높이가 3일 때 최소 노드 개수를 보여 줍니다. 3이지요. 이를 일반화하면 트리 높이가 h일 때 트리의 최소 노드 개수는 h입니다.

이진 트리의 종류를 알아보겠습니다.