트리(tree)는 사이클이 없는 연결 무방향 그래프다. 그림 3-2에 두 그래프가 있는데, 왼쪽 그래프는 트리가 아니고, 오른쪽 그래프는 트리다.

▲ 그림 3-2 그래프와 트리

 

일반적으로 실제 나무를 연상하는 방식으로 트리를 그린다. 노드의 하나를 트리의 루트(root)로 정하고 이 노드에 연결된 노드들을 그린다. 이때 루트에 연결된 노드를 자식 노드(child node)라 부르고, 자식이 없는 노드를 리프 노드(leaf node)라고 한다. 루트의 각 자식 노드는 같은 규칙을 따르는데, 이는 트리에 대한 또 다른 재귀적 정의인 “트리는 루트 노드를 갖는 자료 구조로, 루트 노드는 그에 연결된 노드들의 집합을 가질 수 있다”를 제공한다. 이러한 노드들은 각각 다른 트리의 루트가 된다.