[자료구조] 이진트리

Binary Tree
- 자식노드를 최대 2개로 가지는 트리

Binary Search Tree
- 숫자 기준으로 노드의 왼쪽 자식들은 자신보다 작은 숫자들이 위치하는 것, 반면 우측의 자식들은 자신보다 큰 숫자들이 위치하는 것.
- 숫자가 아닌 우선순위를 기준으로 해도 마찬가지 자신보다 우선순위가 높은 것들은 왼쪽으로 자식을 가지고, 자신보다 우선순위가 낮은 것들을 오른쪽 자식으로 가질 수 있음
- 상황과 형태에 따라 알맞게 구성해야 함.

 

Complete Binary Tree  2:1 or 2:0 완전

- 자식을 가지는 노드 중 하나라도 자식을 2개로 가지는 노드가 있으며됨, 동일한 레벨의 노드가 자식을 1개 혹은 2개를 가짐

Full Binary Tree  2:2 or 2:0 풀
- 자식의 노드를 2개 이상을 가지는 노드가 1개이상이며, 다른 노드의 자식들은 2개의 자식을 갖거나, 갖지 않는 경우의 이진트리를 Full Binary Tree라고 함.

Perfect Binary Tree ALL 2:2 퍼펙트
- 모든 노드가 2개의 자식을 가지는 이진트리

 

완전~ 풀 ~ 퍼펙트!

 

해당 유튜브에서 다양한 정보를 얻을 수 있어서 좋음!

참고: https://www.youtube.com/watch?v=LnxEBW29DOw