포화 이진트리와 완전 이진트리를 알고 가기 이전에, 이진트리 개념을 알아야한다.
노드의 유한집합으로서, 공집합이거나 루트와 왼쪽 오른쪽 서브트리 두 개의 분리된 이진트리로 구성된다.
그럼 포화이진트리는 무엇일까?
이진트리이면서 서브트리까지 모두 빈 곳 없이 꽉찬 트리를 말한다.
노드의 개수는 n = 2^(높이) - 1이다.
포화 이진 트리와 헷갈릴 수 있지만 다르다.
완전 이진트리는 높이가 h 일 때 레벨 h-1까지는 Full BT이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리이다.
노드의 개수는2^(h-1)-1
<=n
<=2^h-1
이다.