트리(Tree)

• 트리란 계층적인 자료를 표현하는데 이용되는 자료구조이다.
• 실제 나무를 거꾸로 한것과 같은 모양을 하고 있기에 트리라고 부른다.
• 트리는 하나의 데이터 아래에 여러 개의 데이터가 존재 할 수 있는 비선형 구조이다.

용어 정리

• 노드(node) : 트리의 구성요소로 트리는 한 개 이상의 노드로 이루어진 유한 집합
• 간선(edge) : 루트와 서브트리를 연결하는 선
• 레벨(Level) : 각 층에 번호를 매기는 것으로, 루트의 레벨은 0이며 내려갈 때마다 레벨이 증가한다.
• 서브트리(sub tree) : 트리 구조의 root에서 뻗어 나오는 큰 트리 내부에 트리 구조를 갖춘 작은 트리.
• 자식(child) : 노드로부터 가지로 연결된 아래쪽 노드.
• 부모(parent) : 노드로부터 가지로 연결된 위쪽 노드.
• 차수(degree) : 노드가 갖는 자식의 수를 차수라고 한다. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다. 예제 트리는 2진 트리이다.