📖 트리

---

• 비선형 구조로 원소들 간에 1:n 관계를 가지는 자료구조
• 원소들 간 계층관계를 갖는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 Tree 모양 구조

특성

• 한 개 이상의 노드로 이루어진 유한 집합
  • 루트(root) : 노드 중 최상위 노드
  • 나머지 노드 : n(>=0)개의 분리 집합 T1,...,Tn 으로 분리
• 이들 T1,...,Tn은 각각 하나의 Tree이며 루트의 부트리(SubTree)라고 함

💬 트리의 구성요소

◾ 노드(node) : 트리의 원소

◾ 간선 : 노드를 연결하는 선

◾ 루트 노드 : 트리의 시작 노드

◾ 형제 노드 : 같은 부모 노드의 자식 노드

◾ 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

◾ 부트리 : 부모 노드와 연결된 간선을 끊었을때 생성되는 트리

◾ 자손 노드 : 부트리에 있는 하위 레벨의 노드

◾ 차수 : 노드에 연결된 자식 노드의 수

◾ 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰값

• 다음 그림의 트리의 차수는 3
  

◾ 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드

• 위에 그림에서 단말 노드는 E, K, G, H, I, J 가 있음

◾ 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨

◾ 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값, 최대 레벨