트리 순회란 무엇인가?
트리 순회(Tree Traversal)는 트리 자료 구조에 포함된 모든 노드를 정확히 한 번씩 방문하는 과정을 의미합니다. 배열이나 연결 리스트처럼 선형적인 자료 구조와 달리, 트리는 계층적(hierarchical) 구조를 가지기 때문에 어떤 순서로 노드를 방문할지 결정하는 것이 중요한 문제가 됩니다.
순회 방식의 분류 기준
트리 순회는 노드를 방문하는 순서에 따라 여러 가지 방식으로 분류됩니다. 대표적인 순회 방법은 다음과 같습니다.
- 전위 순회(Preorder Traversal): 루트 노드를 먼저 방문한 뒤, 왼쪽과 오른쪽 하위 트리를 순서대로 탐색합니다.
- 중위 순회(Inorder Traversal): 왼쪽 하위 트리를 먼저 방문하고, 그 다음 루트 노드, 마지막으로 오른쪽 하위 트리를 방문합니다.
- 후위 순회(Postorder Traversal): 왼쪽과 오른쪽 하위 트리를 모두 방문한 후, 마지막에 루트 노드를 방문합니다.
- 레벨 순회(Level-order Traversal): 트리의 깊이 순서대로, 즉 같은 레벨의 노드들을 왼쪽에서 오른쪽으로 차례대로 방문합니다.
깊이 우선 탐색과 너비 우선 탐색
앞서 소개한 전위·중위·후위 순회는 깊이 우선 탐색(Depth-First Search, DFS)에 속하며, 레벨 순회는 너비 우선 탐색(Breadth-First Search, BFS)에 해당합니다. 자바스크립트에서는 재귀 함수나 스택(Stack), 큐(Queue) 같은 자료 구조를 활용해 이러한 순회 알고리즘을 손쉽게 구현할 수 있습니다.
트리 순회는 DOM 조작, 파일 시스템 탐색, JSON 데이터 처리 등 실제 자바스크립트 개발 환경에서도 폭넓게 활용되는 핵심 개념이므로, 각 순회 방식의 특징과 차이를 정확히 이해해 두는 것이 좋습니다.