자바스크립트 이진 탐색 트리의 중위 순회(Inorder Traversal) 완벽 가이드

중위 순회(Inorder Traversal)는 트리를 순회하는 대표적인 방법 중 하나로, 왼쪽 서브트리를 먼저 방문한 뒤 루트(root) 노드를 거치고, 마지막으로 오른쪽 서브트리를 방문하는 방식입니다. 이때 항상 기억해야 할 점은 모든 노드가 그 자체로 하나의 서브트리가 될 수 있다는 사실입니다.

이진 트리를 중위 순회하면 출력 결과가 키 값의 오름차순으로 정렬된 형태로 나타난다는 특징이 있습니다.

A에서 출발하여 중위 순회 규칙에 따라 왼쪽 서브트리인 B로 이동합니다. B 역시 동일한 방식으로 중위 순회가 진행되며, 이 과정은 모든 노드를 방문할 때까지 계속됩니다. 위 트리를 중위 순회한 결과는 다음과 같습니다.

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

중위 순회 알고리즘

우리가 구현할 알고리즘은 매우 단순합니다.

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

클래스 구현하기

이제 클래스 안에서 실제로 어떻게 구현하는지 살펴보겠습니다. 사용자가 루트 노드를 직접 전달하지 않도록 하기 위해, 클래스 외부에 별도의 헬퍼(helper) 함수를 만들어 활용하는 것이 좋습니다.

inOrder() {
  inOrderHelper(this.root);
}

그리고 클래스 외부에 정의되는 헬퍼 함수는 다음과 같습니다.

헬퍼 함수 예제

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

실행 예제

아래 코드로 직접 테해볼 수 있습니다.

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.inOrder();

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

3
5
7
10
12
15
50

요소들이 정렬된 순서대로 출력되는 것을 확인할 수 있습니다. 그 이유는 왼쪽 서브트리를 가장 먼저 재귀적으로 탐색하기 때문에 자연스럽게 가장 작은 값부터 얻게 되고, 이 과정이 끝까지 반복되면서 모든 요소가 오름차순으로 정렬된 상태로 출력되기 때문입니다.