05-2 이진 트리

※ 이진 트리(Binary Tree)

모든 노드의 차수를 2 이하로 정의하여 전체 트리의 차수가 2 이하가 되도록 만든것.

이진 트리의 서브 트리들 역시 모두 이진 트리이다. 

특정 노드를 기준으로 했을 때 왼쪽 트리 부분을 왼쪽 서브트리라고 하며 오른쪽 트리 부분을 오른쪽 서브트리라 한다.

※ 이진 트리의 특성

1. n개의 노드를 가진 이진 트리는 항상 (n-1)개의 Edge를 갖는다.
2. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1) -1)개가 된다.

※ 이진 트리의 분류

- 포화 이진 트리(Full Binary Tree)

   모든 레벨에 노드가 꽉 차소 포화 상태인 이진 트리

   (2^(h+1)-1)개의 최대 노드수를 갖는 이진 트리

   루트를 1번으로 하고, 레벨 별로 왼쪽에서 오른쪽으로 순서대로 번호를 붙일 수 있다.

- 완전 이진 트리(Complete Binary Tree)

  높이가 h이고 노드 수가 n개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈자리가 없는 트리

  (단, h+1 <= n < 2^(h+1) -1) 즉 노드가 12개면 1번부터 12개까지 번호를 붙일 수 이는 트리

 - 편향 이진 트리(Skewed Binary Tree)

   이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽의 서브 트리만 가지고 있는 트리