7.2.1 전위 순회

전위 순회(preorder traversal)의 방문 순서는 현재 노드->왼쪽 서브 트리->오른쪽 서브 트리입니다.

그림 7-5는 전위 순회에서 방문 순서를 나타냅니다.

▲ 그림 7-5 전위 순회

먼저 루트 노드인 노드 1을 방문하고 그다음 왼쪽 자식을 방문합니다. 그런데 이때 주목해야 할 점은 왼쪽 자식도 자신을 루트로 한 이진 트리라는 것입니다. 그래프에서 이미 서브 그래프(subgraph)를 배웠지요. 이렇게 어떤 노드의 자식이 이루는 트리를 서브 트리(subtree)라고 합니다. 왼쪽 자식을 방문했다는 것은 왼쪽 자식이 루트로 있는 서브 트리의 노드를 모두 방문하는 것입니다. 즉, 루트 노드가 2인 트리의 전위 순회가 됩니다. 느낌이 오나요? 방문을 재귀적으로 수행하는군요. 왼쪽 서브 트리를 모두 방문한 후 마지막으로 오른쪽 자식을 방문합니다. 즉, 오른쪽 서브 트리를 방문합니다. 이렇게 재귀적으로 방문하면 그림 7-5의 이진 트리의 방문 순서는 1-2-4-5-3-6-7이 됩니다. 재귀적인 구조를 가지므로 재귀 함수로 구현할 수 있습니다.