이진 트리 (Binary Tree)

이진 트리 (Binary Tree)

---

  정의 

 

임의의 노드의 자식 노드가, 최대 2개를 넘지 않는 트리

---

  설명 

  컴퓨터 과학에서 정말 많이 사용되는 자료구조이다. 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는다. 또한 이진 트리에서 부트리(Sub-Tree) 또한 이진 트리이다.

•  Root  : Tree의 최상위 노드
•  Parent / Child  : 위 예시에서 임의의 노드 A노드는 B, C 노드의 Parent 이며, B, C 노드는 A 노드의 Child 노드이다.
•  Sibling  : 같은 Parent 노드를 가진 두 노드
•  Leaf Node  : Child 노드가 없는 노드
•  Depth  : 임의의 노드에서, Root 노드 까지의 간선의 수
•  Height  : 최대 Depth의 값
•  Sub Tree  : 트리에서, 임의의 노드를 Root 노드로 삼았을 때 구성되는 또 다른 이진 트리
•  Degree  : 현재 트리에서 임의의 노드가 가질 수 있는 최대 Child 노드의 수

---

  종류 

•  정 이진 트리 (Full Binary Tree)  : 모든 임의의 노드의 Child 노드의 개수가 0 또는 2개인 이진 트리
•  완전 이진 트리 (Complete Binary Tree)  : 마지막 레벨을 제외한 모든 레벨에 해당되는 노드들은 모두 차있고, 마지막 레벨에서 노드들은 왼 쪽 부터 채워진 이진 트리
•  포화 이진 트리 (Perfect Binary Tree)  : 정 이진 트리 이면서 완전 이진 트리이다. 모든 레벨에 노드들이 꽉 차 있다.