완전이진트리, 포화이진트리 개념

이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다.

이를 재귀적으로 표현할 수 있는데,

단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다.

 

완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다.

위 그림에서 볼 수 있듯이,

internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다.

external 노드가 왼쪽부터 차례대로 채워졌으므로

위의 트리는 완전이진트리가 된다.

 

 

만약 왼쪽부터 채우다가 오른쪽 끝까지,

즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다.

 

internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다.

external 노드가 왼쪽부터 차례대로 채우다가

오른쪽 끝까지 모두 채웠으므로

위의 트리는 포화이진트리가 된다.