이진 트리의 종류

이진 트리란? 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다 정 이진 트리 (Full Binary Tree) 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리이다 아래 그림처럼 3의 자식이 하나밖에 없는 경우는 정 이진 트리가 아니다 완전 이진 트리 (Complete Binary Tree) 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 트리이다 마지막 레벨에서는 노드들이 모두 채워질 필요가 없더라도 왼쪽부터 오른쪽으로 노드들이 채워져야 한다 아래 그림처럼 마지막 레벨 직전까지의 레벨이 모두 채워졌지만 마지막 레벨에서 노드가 왼쪽에서부터 채워지지 않은 경우는 완전 이진 트리가 아니다 완전 이진 트리의 높이 완전 이진 트리에는 높이와 관련된 성질이 있다 완전 이진 트리 안에 n개의 ..