이진 트리
- 각 노드가 최대 2개의 자식을 갖는 트리
이진 탐색 트리
- 모든 노드가 모든 왼쪽 자식보다 크거나 같고 모든 오른쪽 자식보다 작은 트리
완전 이진 트리
- 트리의 모든 높이에서 노드가 꽉 차있는 이진 트리
- 마지막 레벨은 꽉 차 있지 않아도 되지만 왼쪽에서 오른쪽으로 채워져야 함
전 이진 트리
- 모든 노드의 자식이 없거나 2개 있는 트리
- 자식이 하나만 있는 노드는 없음
포화 이진 트리
- 전 이진 트리이면서 완전 이진 트리인 트리
- 마지막 단계에서 노드의 개수가 최대가 되어야 함
이진 트리 순회
1) 전위 순회 : 현재 - 왼쪽 - 오른쪽 순서로 방문
2) * 중위 순회 : 왼쪽 - 현재 - 오른쪽 순서로 방문
3) 후위 순회 : 왼쪽 - 오른쪽 - 현재 순서로 방문
현재 노드를 언제 방문하냐를 따져서 이해하면 쉽다.
