트리(Trees)

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

• 리프(Leaf) 노드

• 부모(Parent) 노드와 자식(Child) 노드
• 노드의 수준(level)
• 트리의 높이(Height) = 최대수준(level) + 1, 깊이(depth) 라고도 함
• 부분 트리(서브 트리 - Subtree)
• 노드의 차수(Degree) - 자식(서브트리)의 수

 

이진 트리(Binary Tree)

• 모든 노드의 차수가 2 이하인 트리
• 재귀적으로 정의할 수 있음
  • 루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브트리(단, 이 떄 왼쪽과 오른쪽 서브트리 또한 이진 트리)
• 포화 이진 트리(Full Binary Tree)
  • 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(높이가 k이고 노드의 개수가 $2^{k-1}$ 인 이진 트리)
• 완전 이진 트리(Complete Binary Tree)
  • 높이 k 인 완전 이진 트리
  • 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
  • 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리