Full binary tree
단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리
Perfect binary tree
모든 단말 노드의 깊이가 같은 full binary tree
Complete binary tree
Perfect binary tree에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다. Perfect binary tree의 각 노드에 부모에서 자식으로, 외쪽에서 오른쪽으로 번호를 매겼을 때 perfect binary tree는 아니지만 그 번호가 연속되어 있는 경우이다.
Balanced binary tree
모든 단말 노드의 깊이 차이가 많아야 1인 tree이다. Balanced binary tree는 예측 가능한 깊이 (predictable depth)를 가진다. 노드 개수를 n이라고 하면 길이는 log2n 이 된다.
Order of tree traversal
In-order: 왼쪽 자식 -> 나 -> 오른쪽 자식
Pre-order: 나 -> 왼쪽 자식 -> 오른쪽 자식
Post-order: 왼쪽 자식 -> 오른쪽 자식 -> 나
Level-order: Root -> depth 1인 노드들 -> depth 2인 노드들 -> ...
자료구조
Binary tree는 배열(array)로 표현할 경우 따로 포인터를 가지고 있지 않아도 부모, 자식에 대한 indexing이 가능하다는 장점이 있다.
Root를 0부터 시작하느냐 1부터 시작하느냐에 따라 다른데,
(위 그림에서 처럼) root가 0부터 시작하면, parent index = (my index – 1) / 2, left child index = my index * 2 + 1, right child index = my index * 2 + 2 가 된다.
- Root가 1부터 시작하면, parent index = my index / 2, left child index = my index * 2, right child index = my index * 2 + 1 가 된다.