[자료구조] 이진 트리

이진 트리란?

노드가 최대 2개의 자식을 가질 수 있는 트리

자식노드를 왼쪽자식/오른쪽자식 으로 나누어서 부른다.

이진 트리의 종류

정 이진 트리(Full Binary Tree)

2개 혹은 0개의 자식을 갖는 노드로 이루어진 트리.(자식이 아예 없거나 있으면 무조건 둘이어야 함!)

 

완전 이진 트리(Complete Binary Tree)

1. 마지막 레벨을 제외한 모든 노드가 꽉 채워져 있어야 한다.

2. 마지막 레벨의 노드는 맨 왼쪽부터 채워지는 구조이어야 한다.

 

포화 이진 트리(Perfect Binary Tree)

모든 리프 노드가 같은 높이를 가지고 있으며, 모든 레벨의 노드가 2개의 자식을 가져 노드들이 완벽히 채워져있는 트리.

이진 탐색 트리

이진 트리 이면서,

특정 노드의 왼쪽에 있는 후손 노드들은 특정 노드보다 값이 작고, 오른쪽에 있는 후손 노드들은 특정 노드보다 값이 큰

노드들로 이루어진 트리.