이진 트리

이진 트리는 차수(Degree)가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리를 말합니다.

 

---

이진 트리의 특성

• 이진 트리의 레벨 i에서 최대 노드의 수는 2의 i-1승입니다.
• 이진 트리에서 Terminal Node수가 no, 차수인 2인 노드 수가 n 2 라고 할때 n 0 = n 2 +1이 됩니다.

---

이진 트리의 종류

정이진 트리(Full Binary Tree)

정이진 트리는 깊이가 k일때 전체 노드의 수가 2 k-1개의 노드이고, 레벨 i마다 2 i-1개의 노들들로 꽉찬 트리를 말합니다

 

전이진 트리(Complete Binary Tree)

전이진 트리는 노드의 수가 n개 일때 정이진 트리의 각 노드에 붙인 1~n의 일련 번호와 일대일 대응되는 트리를 말합니다

중간에 빈 부분이 존재하면 전이진 트리가 안됩니다.

 

사향 이진 트리(Skewed Binary Tree)

사향 이진 트리는 루트 노드로 부터 왼쪽 또는 오른쪽으로만 기울어진 트리, 즉 왼쪽 오른쪽 자식이 없는 노드들로만 구성된 트리입니다.

 

왼쪽 사향 이진 트리 : 오른쪽 자식이 없는 노드들로만 구성된 트리

오른쪽 사향 이진 트리 : 위와 반대