• 개요
• 스택, 큐 → 선형 배열 데이터
• 트리 → 이차원

17. 트리 개념

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

• 노드 구성 : 루트 노드, 인터널 노드, 리프 노드
• 부모, 자식, 조상, 후손, 형제 (내 논문에 있었던 것 !!!!!)
• 수준 level

  • 루트 : level 0

    

  • 레벨 수 = 간선의 수

• 트리의 높이 Height = 깊이 depth = 최대 레벨 + 1
  • 위의 사진에서는 4
• 부분 트리 subtree
• 노드의 차수 degree = 자식 서브트리의 수
  • 위의 사진에서는 A의 차수는 2, B의 차수는 1, C의 차수는 2, D의 차수는 3, F의 차수는 1
  • G, H, J, E, K의 차수는 0 (리프 노드)

이진 트리 Binary Tree

: 모든 노드의 차수가 이하인 트리

→ 재귀적으로 정의할 수 있음

빈 트리empty tree이거나 루트 노드 + 왼쪽 서브트리 + 오̤̫른쪽 서브트리

단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리

• 재귀용법에서 유의할 점 : terminal 조건이 없는 종단하지 않는 재귀 호출이 되지 않도록 → 빈 트리도 이진트리라고 봄

포화 이진 트리 Full Binary Tree

: 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리

• 높이가 $k$이고 노드의 개수가 $2^k-1$인 이진 트리

완전 이진 트리 Complete Binary Tree

: 높이 $k$인 완전 이진 트리

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

18. 이진 트리 Binary Trees

• 개요