트리 순회
현재 노드를 언제 기록하는지가 순회 이름을 결정한다
같은 재귀 구조라도 record 위치가 앞, 가운데, 뒤로 움직이면 결과
순서가 완전히 달라집니다.
재귀 프레임 한 장
visit(node) = left + node + right
왼쪽과 오른쪽에는 같은 규칙을 다시 적용하고, null이면 즉시
돌아옵니다.
예시 트리
각 노드의 기록 시점을 비교
Aroot
Bleft
Cright
Dleaf
Eleaf
Fleaf
Preorder
ABDECF
부모를 먼저 기록하므로 구조 복사와 직렬화에 맞습니다.
Inorder
DBEACF
BST에서는 왼쪽, 현재, 오른쪽이 정렬 순서를 만듭니다.
Postorder
DEBFCA
자식을 처리한 뒤 부모를 지우거나 집계할 때 사용합니다.
전위record, visit(left), visit(right)
중위visit(left), record, visit(right)
후위visit(left), visit(right), record