최근 수정:
Tree Traversal. 트리의 순회. 혹은 탐색.
트리도 그래프의 일종이므로 그래프에서 쓰던 탐색 방법을 그대로 사용 가능하다. 하지만 이진 트리는 특수한 경우이므로 3가지의 추가 순회[1]가 가능하다. 아래 항목 참고.
또한, 아래의 Pre-order와 결과적으로 같기도 하다.
또는 Level-order 순회라고도 한다. 학교에서 트리의 순회를 배울 때 BFS보단 이 용어로 배울 것이다.
자식이 최대 2개라는 특성으로 추가적인 순회 방법이 존재한다. 노드의 방문 순서를 기준으로 이름이 붙여졌으며 각각 Pre, In, Post order이다.
구현은 매우 간단하며, 재귀적으로 탐색을 호출하면 된다.
아래 트리 그림 참고 바람.
프리오더. 한글로 전위 순회.
말 그대로 Pre. 해당 노드를 방문 후, 왼쪽 서브트리와 오른쪽 서브트리를 탐색한다.
DFS와 순서가 같다.
그림에서의 순회 순서는 F, B, A, D, C, E, G, I, H
인오더. 한글로 중위 순회.
말 그대로 In. 왼쪽 서브트리를 탐색 후 해당 노드를 방문하고 오른쪽 서브트리를 탐색한다.
그림에서의 순회 순서는 A, B, C, D, E, F, G, H, I
포스트오더. 한글로 후위 순회.
말 그대로 Post. 왼쪽 서브트리와 오른쪽 서브트리를 탐색 후, 해당 노드를 방문한다.
그림에서의 순회 순서는 A, C, E, D, B, H, I, G, F
레벨 오더. 한글로 레벨 순회.
말 그대로 Level. 루트부터의 거리가 같은 노드를 순서대로 탐색한다.
그림에서의 순회 순서는 F, B, G, A, D, I, C, E, H