Tree traversal
전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘은 이진 트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다.
방법
연결 리스트 (Linked list)와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법만이 존재하지만, 트리 구조의 순회에는 많은 방법이 존재한다. 이진 트리의 루트 노드에서 시작해서, 세 가지 주요 단계를 거치며 순회를 진행하는데, 그 단계에는 현재 노드를 방문하는 것, 왼쪽 자식 노드를 순회하는 것과 오른쪽 자식 노드를 순회하는 것이 있다. 이러한 과정은 재귀로 쉽게 설명할 수 있다.
트리 순회를위한 데이터 구조
트리를 순회하려면 어떤 방식 으로든 모든 노드를 반복해야 한다.
주어진 노드에서 두 개 이상의 다음 노드가 있기 때문에 (선형 데이터 구조가 아님) 순차 계산(병렬이 아님)을 가정하면 일부 노드는 나중에 방문하기 위해 어떤 방식 으로든 지연 저장되어야 한다. 이는 종종 스택 (Stack) (LIFO) 또는 대기열 (Queue) (FIFO)을 통해 수행된다.
- 깊이 우선 검색 (Depth-first search)은 스택 (Stack)을 통해 쉽게 구현된다.
- 폭 우선 검색 (breadth-first search)은 대기열 (Queue)을 통해 쉽게 구현된다.
전위 순회
전위 순회(preorder)는 다음과 같은 방법으로 진행한다.
- 노드를 방문한다.
- 왼쪽 서브 트리를 전위 순회한다.
- 오른쪽 서브 트리를 전위 순회한다.
전위 순회는 깊이 우선 검색 (Depth-first search)라고도 한다.
중위 순회
중위 순회(Inorder)은 다음의 순서로 진행된다.
- 왼쪽 서브 트리를 중위 순회한다.
- 노드를 방문한다.
- 오른쪽 서브 트리를 중위 순회한다.
중위 순회는 대칭 순회(symmetric)라고도 한다.
후위 순회
후위 순회(postorder)는 다음과 같은 방법으로 진행한다.
- 왼쪽 서브 트리를 후위 순회한다.
- 오른쪽 서브 트리를 후위 순회한다.
- 노드를 방문한다.
레벨 순서 순회
레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다.
레벨 순서 순회는 너비 우선 순회 (breadth-first search)라고도 한다.