[자료구조] 트리(Tree)

트리(Tree)는 부모에서 자식으로 간선이 연결된 유향 그래프이다.

트리는 재귀로 정의된(Recursively defined) 자기 참조(self-referential) 자료구조이다.

트리는 자식도 트리고, 또 그 자식도 트리이다.
즉, 여러 개의 서브트리(Subtree)가 쌓아 올려져 하나의 큰 트리를 만든다.
이러한 성질 때문에, 트리를 순회할 때 재귀로 순회하는 것이 자연스럽다.

---

트리 vs 그래프

사실 트리는 크게 그래프의 범주에 포함되는 자료구조이다.

트리는 순환 구조를 갖지 않는 그래프이다.
트리와 그래프 사이에서 가장 두드러지는 핵심적인 차이점이다.

• 그래프와 달리, 어떠한 경우에도 한 번 연결된 노드가 다른 노드에 의해 또 다시 연결되는 법이 없다.
• 트리는 부모 노드에서 자식 노드를 가리키는 '단항뱡' 그래프이다.
• 하나의 루트를 제외한 모든 노드는 단 하나의 부모 노드를 갖는다.

---

이진 트리(Binary Tree)

트리 중에서도 모든 노드의 차수가 2 이하인 트리를 이진 트리라고 한다.
모든 노드들이 왼쪽, 오른쪽 최대 2개의 자식 노드를 갖는 형태로, 다진 트리에 비해 훨씬 간결하다.
대체로 트리라고 하면 대부분 이진 트리를 일컫는다.

• 편향(Skewed) 이진 트리
  : 모든 노드의 같은 방향으로만 자식 노드를 가짐.

• 정(Full) 이진 트리
  : 모든 노드가 0개 또는 2개의 자식 노드를 가짐.

• 완전(Complete) 이진 트리
  : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 왼쪽부터 채워져 있음.

• 포화(Perfect) 이진 트리
  : 모든 노드가 2개의 자식 노드를 가지며, 모든 리프 노드가 동일한 깊이 또는 레벨을 가짐.