[Python 자료구조] 트리 (Tree)

⭐ 트리 (Tree)

1. 트리란?

• 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
• 루트(root) 노드, 리프(leaf) 노드, 내부(internal) 노드로 이루어짐
• 노드들 사이에는 부모자식관계가 있다 (부모:뿌리, 자식:나뭇잎)
  
  

2. 트리의 높이 (Height)

• 최대수준(level) + 1
• 깊이 (depth) 라고도 함
  
  

3. 노드의 차수 (Degree)

• 자식 (서브트리)의 수
• degree == 0 → 리프노드
  
  

4. 이진 트리 (Binary Tree)

• 모든 노드의 차수가 2 이하인 트리
• 재귀적으로도 정의할 수 있음
  • 왼쪽, 오른쪽 서브트리가 이진 트리이거나
  • 왼쪽, 오른쪽 서브트리가 빈 트리일 경우 이진 트리라고 볼 수 있다

추상적 자료구조

• size() : 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() : 현재 트리의 깊이 or 높이를 구함
• traversal() : 순회

이진 트리의 순회 (Traversal)

• 깊이 우선 순회 (depth first traversal)
  • 중위 순회
  • 전위 순회
  • 후위 순회
• 넓이 우선 순회 (breadth first traversal)
  
  

5. 포화 이진 트리 (Full Binary Tree)

• 모든 레벨에서 노드들이 모두 채워져있는 이진 트리
• 높이 = k, 노드의 개수 2^k-1인 이진 트리
  
  

6. 완전 이진 트리 (Complete Binary Tree)

• 높이 = k인 완전 이진 트리
• 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
• 레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리