프로그래머스 강의_17

트리 (Trees)

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

• leaf, root 이파리, 뿌리 에서 따온 이름
• root가 위에 있고 가지치기로 마지막이 leaf가 있는 구조
• 루트(Root)노드
• 리프(Leaf)노드 (가지를 치는 노드가 없음)
• 내부(Internal) 노드 (뿌리도 이파리도 아닌 노드)
• 부모(Parent)노드와 자식(Child)노드
• 같은 부모노드를 가지는 자식 노드는 서로 형제간 (sibling)이라 한다
• 조상(ancestor), 후손(descendant) 노드

노드의 수준 (Level)

• 루트 노드는 level 0
• 그다음 노드는 level 1

트리의 높이 (Height)

트리의 높이(height) = 최대 수준(level) + 1, 깊이(depth)라고도 함

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

노드의 차수(Degree)

==> 자식(서브트리)의 수

• degree가 0인 노드는 트리의 leaf nodes가 된다.

이진 트리(Binary Tree)

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

• 재귀적으로 정의할 수 있음.
• 루트노드 + 왼쪽 서브트리 + 오른쪽 서브트리
  (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진트리)

포화 이진 트리(Full Binary Tree)

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

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

완전 이진 트리(Complete Binary Tree)

높이가 k인 완전 이진 트리

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