[C] 포화이진트리, 완전이진트리 차이는 뭘까?

서희찬·2022년 12월 11일
2

자료구조

목록 보기
1/1

포화 이진트리와 완전 이진트리를 알고 가기 이전에, 이진트리 개념을 알아야한다.

이진트리는

노드의 유한집합으로서, 공집합이거나 루트와 왼쪽 오른쪽 서브트리 두 개의 분리된 이진트리로 구성된다.

그럼 포화이진트리는 무엇일까?

포화이진트리(Full BT)

이진트리이면서 서브트리까지 모두 빈 곳 없이 꽉찬 트리를 말한다.
노드의 개수는 n = 2^(높이) - 1이다.

완전 이진 트리(Complete BT)


포화 이진 트리와 헷갈릴 수 있지만 다르다.
완전 이진트리는 높이가 h 일 때 레벨 h-1까지는 Full BT이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리이다.
노드의 개수는 2^(h-1)-1 <= n <= 2^h-1이다.

profile
부족한 실력을 엉덩이 힘으로 채워나가는 개발자 서희찬입니다 :)

0개의 댓글