[ ADT 7-1 ]은 이진 트리의 데이터와 기본 연산을 논리적으로 정의한 추상 자료형이다.

이진 트리의 추상 자료형에 따라 만들어진 이진 트리는 다음과 같은 특징을 갖는다.

• 노드가 n개인 이진 트리는 항상 간선이 (n-1)개이다.

  이진 트리에서 루트를 뺀 나머지 노드는 부모 노드를 하나 가지므로 부모 노드와 연결하는 간선을 한 개 갖는다. 따라서 노드가 n개인 이진 트리에서 루트를 제외한 나머지 n-1개의 노드가 간선을 각각 한 개 가지고 있으므로 이진 트리에는 항상 간선이 n-1개 존재한다.

• [ ] 높이가 h인 이진 트리가 가질 수 있는 노드 개수는 최소 (h+1)개이며, 최대 (2의(h+1)승-1)개이다.

  이진 트리 높이가 H가 되려면 한 레벨에 (a)와 같이 최소한 한 개의 노드가 있어야 하고, 레벨이 0부터 시작하므로 높이가 h인 이진 트리의 최소 노드 개수는 h+1개가 된다. 하나의 노드는 (b)와 같이 자식 노드를 최대 두 개 가질수 있으므로 레벨 i에서는 최대 노드 개수는 2의 i승 개가 된다. 따라서 높이가 h인 이진 트리 전체의 최대 노드 개수는

  

  이 된다.