이진 트리

이진 트리 (binary tree) :  부모노드에 자식노드가 두 개 이하인 트리

---

완전 이진 트리(Complete Binary Tree) : 노드가 왼쪽부터 채워지고, 마지막 레벨을 제외하고 모든 노드가 채워져 있는 이진 트리

 

 

완전 이진 트리는 2가지 조건을 충족해야 한다

첫째,  마지막 레벨(level)을 제외하고 모든 노드가 채워져있어야 한다.

마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐수도 있다.

둘째,  노드는 왼쪽에서 오른쪽 방향으로 채워져야 한다. 
그래서 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자식도 가지고 있어야 완전이진트리로 볼 수 있다.

 

---

포화 이진 트리 (표준 표현 : Perfect Binary Tree ,   비표준 표현 : Fully Complete Binary Tree)

 

쉽게 말해  꽉 찬 이진 트리

이진 트리 중에서   모든 노드가 2개의 자식을 가지고 leaf 노드가 모두 같은 레벨인 트리

 

 

---

 

참고)

자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기

자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기