이진 트리

트리 중에는 우리가 앞으로 두 장에 걸쳐서 다루게 될 아주 중요한 트리가 있는데, 이것을 알아보겠습니다. 바로 이진 트리(binary tree)입니다. 이진 트리란 트리를 구성하는 노드의 자식이 최대 두 개인 트리를 의미합니다. 그럼 모든 노드를 아예 자식이 없는 경우, 자식을 하나 가진 경우, 자식을 둘 가진 경우로 나눌 수 있겠지요. 자식이 둘이므로 왼쪽 자식과 오른쪽 자식으로 구분합니다.

이진 트리가 가지는 몇 가지 재미있는 수식을 알아볼까요?

다음 그림은 이진 트리의 예입니다.

▲ 그림 7-2 이진 트리

레벨 3에서 최대 노드 개수는 몇 개일까요? 최대 노드 개수이므로 루트 노드 1도 두 자식을 가지고 레벨 2의 두 자식도 모든 자식을 가질 때, 레벨 3에서 노드 개수를 말하는 것입니다. 그림으로 확인해 보면 네 개입니다. 이를 일반화하면 어떤 레벨 l에서 최대 노드 개수는 다음과 같습니다.

2^ㅣ-1

레벨 4를 이 식에 대입해 보면 2³이므로 여덟 개가 됩니다.