트리(Trees)

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

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

노드의 수준(Level)

부분 트리(서브트리 - Subtree)

노드의 차수(Degree)

---

이진 트리(binary trees)

• 모든 노드의 차수(degree)가 2이하인 트리
• 재귀속성이 있음
• 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
  (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리→ 재귀 속성의 종단 조건)

포화 이진 트리(full binary tree)

• 모든 레벨에서의 노드들이 모두 채워져 있는 이진트리를 말한다. 포화 이진 트리는 높이가 K이고 노드의 개수가 2^K -1개인 이진트리라는 속성을 가진다

완전 이진 트리(complete binary tree)

• 높이 k인 완전 이진트리는 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진트리로 구성
• 단, 마지막 레벨 k-1에 풀로 채워져 있지 않더라도 왼쪽부터 노드가 순차적으로 채워져 있다면
  완전 이진 트리(complete binary tree)