트리

정점 (node) 과 간선 (edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료구조

• 뿌리 (root)
• 잎 (leaf)

통상 뿌리가 위에 있고, 밑으로 뻗어나가는 이미지로 그려진다.

맨 위의 노드: 루트 노드

맨 밑의 더 이상 자식 노드를 갖지 않는 노드: 리프 노드

뿌리도 잎도 아닌 노드: 내부 (Internal) 노드

부모 (Parent) 노드와 자식 (Child) 노드

• 서로 간선으로 연결되어 있고, 뿌리쪽에 가까운 노드를 부모, 먼 노드를 자식이라고 한다.
• 같은 부모를 가진 자식 노드들은 형제 관계 (sibling) 이라고 한다.

부모의 부모… —> 조상 (ancestor)

자식의 자식… —> 후손 (descendant)

노드의 수준 (Level)

루트 = level 0

그 다음 = level 1