-
이진트리란
리프 노드를 제외한 노드의 자식이 1개 혹은 2개로 이루어진 트리를 말한다.
즉, 리프 노드를 제외한 모든 노드는 다음의 구조를 지녀야 한다.
※ 각 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 구분하며 각각의 자식 노드가 자식 노드를 가진 경우 자식 노드를 루트로 하는 노드 집단을 서브 트리라고 한다.
이진트리는 다음과 같은 특징을 가진다.
- n개의 노드를 진 경우 n-1 개의 간선을 가진다.
- 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 h-1 개이며 최대 개수는 2^(h+1)-1 개가 된다.