Traversal timing

순회 이름보다 값을 기록하는 시점 우선 선택

같은 재귀 구조라도 현재 노드를 언제 기록하는지에 따라 결과가 달라진다.

Pre

전위

현재 값을 먼저 기록해 구조 복사나 직렬화에 쓴다.

In

중위

왼쪽 처리 뒤 현재를 기록해 BST 정렬 결과를 만든다.

Post

후위

자식을 모두 처리한 뒤 기록해 삭제와 집계에 맞다.

예시 트리 1(2(4,5),3)

전위 1 2 4 5 3
중위 4 2 5 1 3
후위 4 5 2 3 1
반복 스택
레벨 큐