이진 트리

• 트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의
• 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐
• 부모 노드와 자식 노드 수와의 관계 → 1:2
• 공백 노드도 자식 노드로 취급
• 0 ≤ 노드의 차수 ≤ 2

• 이진 트리는 순환적 구성
  • 노드의 왼족 자식 노드를 루트로 하는 왼쪽 서브 트리도 이진 트리
  • 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리