그림 3-3을 보면 왼쪽 트리는 정상적인 나무처럼 위로 자라고, 오른쪽 트리는 같은 트리인데 아래로 자란다. 컴퓨터에서 트리는 아래로 자라는 트리다.

▲ 그림 3-3 위와 아래로 자라는 트리

 

한 노드의 자식 노드 수를 노드의 차수(degree)라고 부른다. 이진 트리(binary tree)를 한번 살펴보자. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖고, 차수가 최대 2인 트리다. 정확하게 정의하면 이진 트리는 최대 두 개의 노드로 연결된 루트 노드가 있는 자료 구조다. 각 자식 노드는 다른 이진 트리의 루트 노드가 된다.

트리는 구조 때문만 아니라 각 노드가 데이터를 담을 수 있어서 유용하다. 데이터는 노드의 유효한 내용물이며, 자식 노드의 데이터와 어떤 관계가 있다. 이것은 트리의 계층 구조를 반영한 계층적 관계다.