[알고리즘/자료구조] 트리

0. 🔖 목차

1. 트리 자료구조
   1-1 트리 개념 및 용어
   1-2 이진 트리

1. 트리 자료구조

1-1. 트리 개념 및 용어

트리란 그래프 자료구조중 하나로 그래프 내의 모든 경로에 순환(Cycle)이 없으면 이를 트리라고 한다.

• 루트 노드(Root Node): 트리의 최상위에 위치한 부모가 없는 노드
• 리프 노드(Leaf Node): 트리의 최하위에 위치한 자식이 없는 노드(단말 노드, Terminal Node라고도 함)
• 서브트리(Subtree): 특정 노드 하위에 구성된 트리
• 부모 노드(Parent Node): 특정 노드의 직속 상위 노드
• 자식 노드(Child Node): 특정 노드의 직속 하위 노드, 이진트리에서 자식노드는 방향성이 있음(오른쪽, 왼쪽 자식을 따로 구분함)
• 깊이(Depth): 특정 노드가 루트 노드까지 걸리는 엣지 수(루트 노드는 깊이가 0)
• 높이(Height): 특정 노드가 하위 리프 노드까지 걸리는 최대 엣지 수
• 레벨(Level): 특정 노드의 깊이에 1을 더한 값(루트 노드는 레벨이 1)

1-2 이진 트리

각 노드가 최대 두 개의 자식을 가질 수 있는 트리.

• 완전 이진 트리
  

마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있고 마지막 레벨의 노드들이 가능한 가장 왼쪽에 있는 트리.

• 포화 이진 트리
  

모든 레벨에 노드가 꽉 차있는 트리. 모든 포화 이진 트리는 완전 이진 트리임.