트리의 모든 노드를 한 번씩 방문하는 방법. 이진 트리에서는 현재 노드를 언제 방문하느냐에 따라 세 가지로 갈린다. 왼쪽 서브 트리를 먼저 돌고 오른쪽을 나중에 도는 것은 셋 다 같고, 자기 자신을 그 사이 어디에 끼우느냐만 다르다.
방문 시점이 정하는 순회 종류
전위 순회는 자기 자신을 보고 왼쪽과 오른쪽으로 내려가고, 중위 순회는 왼쪽을 다 돈 뒤 자기 자신을 보고 오른쪽으로 가며, 후위 순회는 양쪽을 다 돈 뒤에야 자기 자신을 본다. 셋 다 재귀로 쓰면 세 줄의 순서만 바꾸면 된다.
static void inorder(Node node) {
if (node == null) return;
inorder(node.left);
visit(node); // 이 줄의 위치가 곧 순회 종류
inorder(node.right);
}중위 순회
이진 탐색 트리를 중위 순회하면 정렬된 순서로 나온다. 탐색 트리는 “왼쪽은 전부 작고 오른쪽은 전부 크다”는 규칙을 지키므로, 왼쪽부터 자기, 오른쪽 순으로 도는 것이 곧 작은 값부터 큰 값 순으로 도는 것이다. 별도로 정렬하지 않아도 순회만 하면 오름차순이 나온다.
해시 테이블에는 없는 성질이고, 정렬된 순회가 필요할 때 탐색 트리를 고르는 이유다.
전위 순회
위에서 아래로 내려가며 처리해야 할 때 쓴다. 트리를 그대로 복제하거나 디렉터리 구조를 출력하는 일이 그렇다.
후위 순회
자식을 다 처리해야 부모를 처리할 수 있을 때 쓴다. 디렉터리 용량을 계산하거나 트리를 메모리에서 해제하는 일이 그렇다. 자식을 지우기 전에 부모를 지우면 자식에 접근할 방법이 사라진다.
레벨 순회
세 가지 외에 레벨 순서로 도는 방법도 있다. 이건 재귀가 아니라 큐를 쓰는데, 트리에 BFS를 돌리는 것과 같다.