먼저 확장 이진 트리(extended binary tree)를 알아보겠습니다. 이 트리는 모든 빈 노드를 외부 노드(external node)로 대체합니다. 이렇게 되면 이전에 리프 노드였던 노드들은 리프 노드가 아니게 됩니다. 그 역할을 외부 노드가 물려받기 때문이지요. 이때 외부 노드를 제외한 모든 노드는 내부 노드(internal node)가 됩니다.

그림으로 확인해 볼까요? 그림 9-2는 확장 이진 트리입니다. 앞으로 외부 노드는 사각형으로, 내부 노드는 이전처럼 원으로 표현하겠습니다.

▲ 그림 9-2 확장 이진 트리