트리(Trees)

• 스택, 큐: 1차원 자료구조
• 트리: 2차원 자료구조

트리(Tree)

• 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
• 뿌리(root)&이파리(leaf) (거꾸로된 나무 모양 )

루트/리프/내부 노드

• 루트(Root) 노드: 맨 위의 노드
• 리프(Leaf) 노드: 더 이상의 가지가 없는 마지막 노드
• 내부(Internal) 노드: 루트, 리프도 아닌 내부의 노드

부모/자식/형제간 노드

• 부모 노드: 더 뿌리쪽에 있는 node
• 자식 노드: 더 이파리에 있는 노드
• 형제간(sibling) 노드: 같은 부모에 딸린 자식 노드

조상/후손 노드

• 조상(ancestor): 부모의 부모(의 부모의 ...)
• 후손(descendant): 자식의 자식(의 자식의 ...)

노드의 수준(Level)

• 루트 노드: level 0 (level 1로 설정 가능)
• 그 다음 노드: level 1 그 다음 level 2 ...

트리의 높이/깊이(Height/depth)

• 최대 수준(level) + 1

부분/서브 트리, 노드의 차수

• 부분 트리(서브트리 - Subtree): 트리를 쪼개어 서브 트리
• 노드의 차수(Degree): 자식(서브트리의 수), 어느 한 노드 시점에서 자식으로 연결되는 간선의 수
• degree = 0 인 노드는 leaf nodes
• 루트 노드를 제외한 어느 노드에서 자식 노드는 여러 개 일 수도 있지만 부모 노드는 1개라는 게 트리 구조의 특징

이진 트리/포화 이진 트리/ 완전 이진 트리

• 이진 트리(Binary tree): 모든 노드의 차수가 2 이하인 트리

  • 재귀 적으로 정의 가능: 빈트리(empty tree)이거나, 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리)

• 포화 이진 트리(Full Binary Tree)

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

• 완전 이진 트리(Complete Binary Tree)

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