[프로그래머스 강의] 17강 트리

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

트리(Tree)

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

✔ 부모의 부모(의 부모의...) - 조상(ancestor)

✔ 자식의 자식(의 자식의...) - 후손(descendant) 

 

 

트리의 높이(Height)

트리의 높이(height) = 최대수준(level) + 1

 

트리의 높이는 깊이(depth)라고도 한다.

 

부분트리(서브트리, SubTree)

노드의 차수(Degree) = 자식(서브트리)의 수

degree 가 0인 노드는 leaf 노드이다. 

 

이진트리(Binary Tree)

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

이진트리는 재귀적으로 정의할 수 있다.

 

✔ 빈 트리(Empty Tree)이거나 

✔ 루트노드 + 왼쪽 서브트리 + 오른쪽 서브트리(단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리)

 

포화 이진트리(Full Binary Tree)

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

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

완전 이진 트리(Complete Binary Tree)

높이가 k인 완전 이진 트리 인 경우,

✔ 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리 

✔ 레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리