[자료구조/java] 이진 트리 (Binary Tree)

* 이진 트리 (Binary Tree)

"노드의 차수를 2 이하로 정하여 트리의 노드구조를 일정하게 정의함으로써 연산을 단순화 시킨 트리"

- 이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있다. (공백 노드도 이진 트리의 노드로 취급)

- n개의 노드를 가지는 이진 트리는 항상 (n-1)개의 간선을 가진다.

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

* 이진 트리 (Binary Tree)의 분류

포화 이진 트리(Full Binary Tree)

- 모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미

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

완전 이진 트리(Complete Binary Tree)

- 높이가 h 고, 노드 수가 n개일 때(단, n<2^(h+1)-1), 노드의 위치가 포화 이진 트리의 노드 1번부터 n번까지 완전히 일치하는 이진 트리이다. 따라서 완전 이진트리에서는 (n+1)번부터 2^(h+1)-1번까지의 노드는 공백 노드가 된다.

편향 이진 트리(Skewed Binary Tree)

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