Binary Tree

degree가 최대 2인 트리

i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)

• 주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.

k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1

위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임

binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음

Full (Perfect) Binary Tree

마지막 레벨까지 노드가 꽉 차게 있는 트리

Complete Binary Tree

노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리

위 그림에서 3번 노드가 없어도 complete binary node는 성립하지만 1번이나 2번 노드가 없으면 complete binary tree가 아니게 됨. 

Skewed Tree

binary tree를 구현하는 데엔 array로 구현하는 것이 좋지만 다른 트리에서는 효율성이 떨어지고 컴파일 언어에서 어레이 사이즈 제한때문에 저장공간 문제가 존재. C에서는 이를 linked list로 해결할 수 있음. (근데  linked list는 구현이 어려움)

Binary Tree Traversal

루트노드에서 시작해 linear 하게 노드를 1번씩 방문하는 방식은 아래와 같습니다.

V: 노드 방문 L: 왼쪽 branch를 타고 이동 R: 오른쪽 branch를 타고 이동

• inorder: LVR (Left Visit Right)
• preorder: VLR (Visit Left Right)
• postorder: LRV (Left Right Visit)

예를 들어, preorder는 하위 트리를 탐색하기 전에 노드 방문이 완료

예시 (inorder: LVR)

1. 루트노드인 X에서 시작.
2. 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 Y 노드로 이동
3. Y 노드에서도 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 S 노드로 이동
4. S 노드에는 왼쪽 브랜치가 없어서 이동할 수 없음. 
5. 왼쪽으로 이동할 수 없으므로 S 노드를 방문 후 오른쪽 브랜치로 이동하려하나 브랜치가 없어 Y노드로 롤백
6. Y노드를 방문한 후 오른쪽 브랜치를 타고 이동하여 T 노드로 이동
7. T노드는 4~5번과 동일.

위와 같은 순서로 값의 출력은 S, Y, T, X, Z 순으로 출력됨

위와 같이 binary tree의 모든 노드를 탐색하는 방법은 stack이 필요함. 

모든 노드를 탐색하는데에 걸리는 time complexity는 O(N)임 (N은 트리에 존재하는 노드의 개수)