2.2이진 트리

■ 이진 트리

이진 트리는 한 노드가 자식 노드를 두 개 이하만 갖는 트리입니다. 노드는 이전 장에서 연결 리스트를 공부했기 때문에 어느 정도 짐작이 갈 것입니다. 이진 트리의 노드도 데이터 부분과 참조 부분으로 이루어져 있습니다. 다만 참조가 두 개입니다. 왼쪽 자식 노드를 가리키는 참조와 오른쪽 자식 노드를 가리키는 참조입니다.

■ 부모 노드와 자식 노드

이진 트리를 구성하는 요소에는 크게 부모 노드(parent node)와 자식 노드(child node)가 있습니다.

그림 13-7에서 1 노드는 부모 노드, 2 노드는 1 노드의 왼쪽 자식 노드, 3 노드는 1 노드의 오른쪽 자식 노드입니다. 어떤 의미인지는 직관적으로 알 수 있습니다.

그림 13-7 트리의 구성 ①