트리

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

• 노드 : 트리의 원소

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

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

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

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

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

• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

• 차수 :

  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  • 단말 노드 : 차수가 0인 노드. 자식 노드가 없는 노드

• 높이 :

  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨

• 포리스트 : 서브트리의 집합