트리(tree)는 자료들이 리스트, 스택, 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이다. 또한 계층 관계로 만들어진 계층형 자료구조(Hierarchical Data Structure)이다. 가족 관계는 계층적인 관계를 가지고 있으므로 트리 자료구조의 예이기도 하다.

[ 그림 7-1 ]은 길동이네 가족 관계를 나타낸 가계도이다.

가계도에서 가족 구성원을 연결하는 선은 부모-자식 관계를 나타낸다. 길동이에게는 자식이 세 명(진호, 영주, 성호), 진호에게는 두 명(상원, 상범), 영주에게는 한 명(동혁), 성호에게는 세 명(형준, 형진, 민정) 있다. 또 상범이에게는 자식이 두 명(수영, 수철) 있다. 부모가 같은 자식들은 형제 관계가 된다. 따라서 진호, 영주, 성호는 부모가 모두 길동이이므로 형제 관계이다.

조상은 자신과 연결된 선을 따라 위로 올라가면서 만나는 사람들이다. 예를 들어, 수영이의 조상은 상범, 진호, 길동이다. 마찬가지로 자손은 자신과 연결된 선을 따라 아래로 내려가면서 만나는 사람들이다. 따라서 진호의 자손은 상원, 상범, 수영, 수철이다. 가계도의 시작(루트)인 길동이를 0세대(레벨 0)라고 하면 길동이 자식들은 1세대(레벨 1), 그 다음 자식들은 2세대(레벨 2), 그 다음 자식들은 3세대(레벨 3)가 된다. 가족 구성원 누구든지 분가하여 독립된 가계를 이룰 수 있다.

트리의 구조와 구성 요소도[그림 7-1]의 가계도와 같다. 트리를 구성하는 원소(자료)를 노드(Node)라 하고, 노드를 연결하는 선은 간선(Edge)이라고 한다.

[ 그림 7-2 ]의 트리 A에는 노드가 A, B, C, D, E, F, G, H, I, J, K, L로 열두 개 있고, 부모(Parent) 노드와 자식(Child) 노드는 간선으로 연결되어 있다. 트리의 시작 노드를 루트(Root) 노드라고 하며, 루트는 레벨(Level) 0이 된다. 같은 부모 노드를 가진 자식 노드들은 서로 형제(Sibling)노드가 된다. 노드 A의 자식 노드인 노드 B, C, D는 서로 형제 노드가 된다. 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 노드는 모두 그 노드의 조상(Ancestor)노드가 된다. 노드 K의 조상 노드는 노드 F, B, A가 된다.

자식 노드들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드는 자식 노드 수만큼 서브 트리(Subtree)를 갖는다. [ 그림 7-2 ]에서 노드 A는 자식 노드로 B, C, D를 가지므로 서브 트리 역시 세 개이다. 한 노드의 자손 노드는 그 노드의 서브 트리에 있는 노드가 된다. 노드 B의 자손 노드는 서브 트리 E의 노드와 서브 트리 F의 노드이므로 E, F, K, L이 된다.

한 노드가 가지는 서브 트리의 수, 즉, 자식 노드 수를 노드의 차수(Degree)라고 한다. [ 그림 7-2 ]에서 노드 A의 차수는 3, 노드 B의 차수는 2, 노드 C의 차수는 1, 노드 D의 차수는 3이다. 차수가 0인 노드, 즉 자식 노드가 없는 노드를 단말(Terminal) 노드 또는 리프(Leaf) 노드라고 한다. 따라서 노드 E, G, H, I, J, K, L은 트리 A의 단말 노드이다. 단말 노드를 제외한 나머지 노드, 즉 차수가 1 이상인 노드는 내부(Internal)노드라고 한다. 노드의 차수 중에서 가장 큰 값이 트리의 차수가 되므로 트리 A의 차수는 3이 된다.

한 노드의 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수이고, 노드의 높이 중에서 가장 큰 값, 즉 최대 레벨이 트리의 높이가 된다. [ 그림 7-2 ]에서 노드 B의 높이는 1, 노드 F의 높이는 2이며, 트리 A의 전체 높이는 3이다.

나무가 모이면 숲이 되듯 여러 개의 트리 집합을 포리스트(Forest)라 한다. n개의 자식 노드, 즉 n개의 서브트리를 가진 루트 노드를 제거하면 n개로 분리된 트리가 포리스트를 이룬다. [ 그림 7-2 ]의 트리 A에서 루트 노드 A를 제거하면 [ 그림 7-3 ]과 같이 A의 자식 노드인 B, C, D는 각각 분리된 트리의 루트가 되고 이들 트리들의 집합이 포리스트가 된다.