3.5트리의 순회

트리의 모든 노드를 중복하지 않으면서 방문하는 것을 순회(traversal)이라고 합니다. 데이터를 저장만 하고 찾을 수 없다면 아무 소용이 없겠지요. 그만큼 순회는 굉장히 중요한 개념입니다.

순회하는 방법에는 세 가지가 있습니다.

1| 전위 순회(preorder traversal)
노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리

2| 중위 순회(inorder traversal)
왼쪽 서브 트리 → 노드 → 오른쪽 서브 트리

3| 후위 순회(postorder traversal)
왼쪽 서브 트리 → 오른쪽 서브 트리 → 노드

전위 순회든 중위 순회든 후위 순회든 왼쪽 서브 트리와 오른쪽 서브 트리가 들어 있습니다. 우리의 목적은 모든 노드를 방문하는 것이므로 서브 트리의 모든 노드도 방문해야 합니다. 어떻게 해야 할까요? 바로 재귀를 통해 모든 노드를 방문합니다. 서브 트리도 이진 트리이므로 서브 트리에서도 순회마다 순서를 맞춰 재귀적으로 노드를 방문하는 것입니다.