- Full Binary Tree (정 이진 트리) : 모든 트리의 자식은 0개 또는 2개다.
- Perfect Binary Tree (포화 이진 트리) : 모든 리프노드의 높이가 같다.
- Complete Binary Tree (완전 이진 트리) : 트리의 원소를 왼쪽에서 차례대로 채워넣은 형태.
- 모든 리프노드의 높이는 최대 1 차이
- 노드의 오른쪽 자식이 있으면 반드시 왼쪽 자식도 존재
- n개 원소로 이뤄진 완전이진트리는 n개 원소의 배열로 표현할 수 있다.
- n번째 원소의 왼쪽 자식은 2n 번째, 오른쪽 자식은 2n+1 번째 원소이다.
- n번째 원소의 부모 노드는 [n/2] 번째 원소이다.
- In-order Traversal (중위 순회) : 왼쪽 자식, 자신, 오른쪽 자식 순으로 순회
- Pre-order Traversal (전위 순회) : 자신, 왼쪽 자식, 오른쪽 자식 순으로 순회
- Post-order Traversal (후위 순회) : 왼쪽 자식, 오른쪽 자식, 자신 순으로 순회
이진탐색트리를 중위순회(in-order)하면 정렬된 값들을 얻을 수 있다.