이진 트리

트리의 개념과 용어
node
edge
path
length
height
level
leaf node
internal node
root node

트리의 속성
1. 루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다.
2. 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다
3. 회로(cycle)이 존재하지 않는다.
4. 모든 노드는 서로 연결되어 있다.
5. 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
6. 엣지(edge)의 수는 노드의 수에서 1을 뺀 것과 같다.

이진트리란 (Binary Tree)
자식노드가 최대 두개인 노드들로 구성된 트리
정이진트리(full ~) : 모든 레벨에서 노드들이 꽉 채워짐
완전이진트리(complete ~) : 마지막 레벨 제외 모든 레벨에서 노드들이 꽉 채워짐
균형이진트리(balanced ~) : 모든 잎새노드의 깊이 차이가 많아야 1임

트리 순회 (Tree Traversal)
트리의 각 노드를 체계적인 방법으로 방문하는 과정
하나도 빠뜨리지 않고 한번만 중복 없이 방문해야 함
전위순회(preorder) : 노드 → 왼쪽 → 오른쪽
중위순회(inorder) : 왼쪽 → 노드 → 오른쪽
후위순회(postorder) : 왼쪽 → 오른쪽 → 노드