트리:완전 트리와 정 트리

들어가기 전에

완전 트리와 정 트리에 대해 살펴보도록 하겠습니다.

 

학습 목표

완전 트리와 정 트리의 정의를 설명할 수 있습니다.

 

핵심 단어

• 완전 트리
• 정 트리

 

트리:완전 트리와 정 트리

 

Complete / Full

 

Every non leaf has two children except for the last row & the last row is filled left -> right

 

Every non leaf has two children & all the leaves are on the same level 

 

 

완전 트리 (Complete Tree): 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리입니다.

 

정 트리 (Full Tree): 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고 모든 잎이 같은 레벨에 있는 트리입니다.

 

 

잎 : 맨 마지막 레벨에 있는 노드

 

 

생각해보기

1) 완전 트리와 정 트리의 공통점과 차이점은 무엇인가요?

 

공통점은 잎이아닌 노드가 2개의 자식 노드를 가지고있다.

차이점은 완전 트리는 모든 잎이 같은 레벨에 있지 않지만 정 트리는 모든 잎이 같은 레벨에 있다.

 

 

출처 : https://www.boostcourse.org/cs204/lecture/626047?isDesc=false