리스트는 순서를 매긴 데이터를 나열하는 자료 구조라면, 트리는 데이터 사이의 계층 관계를 표현하는 자료 구조이다.

트리

트리는 노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다.

루트

루트는 트리에서 가장 상단에 위치한 노드이다. 트리당 하나 존재한다.

리프

가장 아래쪽에 있는 노드로, 단말노드, 외부노드라고 한다.
더이상 가지가 뻗어나갈 수 없는 마지막에 존재하는 노드를 의미한다.

비단말 노드

리프를 제외한 모든 노드를 비단말 노드라고 부른다. 내부노드라고도 부른다.

부모

가지로 연결된 노드 중 바로 위에 연결된 노드를 의미한다. 루트노드는 부모를 가지지 않는다.

자식

가지로 연결된 노드 중 바로 아래에 연결된 노드를 의미한다.

형제

가지로 연결된 노드 중 같은 부모를 가진 노드를 의미한다.

조상

어떤 노드 기준으로 위로 가지에 의해 연결된 모든 노드를 의미한다.

레벨

가장 상단에 위치한 루트노드는 레벨 0이다.

높이

루트에서 가장 먼 리프까지의 거리이자 리프 레벨의 최댓값을 높이라고 한다.

차수

각 노드가 가진 자식노드의 개수를 의미한다.
모든 노드의 차수가 2이하이면 이진 트리이다.