자바스크립트 트리 순회: 전위 순회(Pre-order Traversal) 완벽 정리

전위 순회(Pre-order Traversal)는 트리를 탐색하는 대표적인 방법 중 하나로, 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문합니다. 즉, 각 노드에 도달했을 때 자기 자신을 먼저 처리한 뒤 자식 노드들을 탐색하는 것이 특징입니다.

전위 순회의 동작 원리

아래 트리 구조를 예로 들어 살펴보겠습니다.

루트 노드 A에서 시작한다고 가정해 봅시다. 전위 순회 규칙에 따라 먼저 A 자신을 방문하고, 그다음 왼쪽 서브트리인 B로 이동합니다. B 역시 같은 규칙으로 순회되며, 이 과정은 트리의 모든 노드를 방문할 때까지 반복됩니다.

이 트리를 전위 순회한 결과는 다음과 같습니다.

A → B → D → E → C → F → G

전위 순회 알고리즘

전위 순회를 코드로 구현할 때의 핵심 로직은 아래 세 단계로 요약할 수 있습니다.

현재 노드의 데이터를 출력(처리)한다.
왼쪽 서브트리를 재귀적으로 순회한다.
오른쪽 서브트리를 재귀적으로 순회한다.

이제 이 알고리즘을 클래스 메서드 형태로 어떻게 구현하는지 살펴보겠습니다.

자바스크립트 구현

먼저 외부에서 호출하는 preOrder() 메서드입니다.

preOrder() {
    preOrderHelper(this.root);
}

실제 순회 로직을 담당하는 헬퍼 함수는 다음과 같습니다.

예제: 헬퍼 함수

function preOrderHelper(root) {
    if (root !== null) {
        console.log(root.data);
        preOrderHelper(root.left);
        preOrderHelper(root.right);
    }
}

헬퍼 함수는 현재 노드가 null이 아닌 경우에만 동작하며, 노드 데이터를 출력한 후 왼쪽과 오른쪽 자식을 차례로 재귀 호출합니다. 이처럼 재귀 구조를 활용하면 복잡한 트리도 간결한 코드로 순회할 수 있습니다.

동작 확인하기

구현한 코드가 올바르게 작동하는지 이진 탐색 트리(Binary Search Tree)를 만들어 직접 테스트해 보겠습니다.

예제: 테스트 코드

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.preOrder();

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

출력 결과를 보면 루트 노드 10이 가장 먼저 처리되고, 이후 왼쪽 서브트리(5, 3, 7)와 오른쪽 서브트리(15, 12, 50)가 순서대로 방문된 것을 확인할 수 있습니다. 이것이 바로 전위 순회의 핵심 특징입니다.

정리

전위 순회는 트리를 복사하거나 직렬화(serialization)할 때 특히 유용하게 사용됩니다. 루트를 먼저 방문하기 때문에 트리 구조를 그대로 재현하기에 적합하기 때문입니다. 중위 순회(In-order), 후위 순회(Post-order)와 함께 트리 탐색의 기본기를 확실히 익혀두면 다양한 알고리즘 문제 해결에 큰 도움이 됩니다.