자바스크립트 트리 후위 순회(Post-order Traversal) 완벽 가이드

후위 순회(Post-order Traversal)란?

후위 순회는 루트 노드를 가장 마지막에 방문하는 트리 순회 방식으로, 메서드의 이름 역시 여기서 유래했습니다. 순회 순서는 다음과 같습니다.

• 먼저 왼쪽 서브트리를 순회합니다.
• 그다음 오른쪽 서브트리를 순회합니다.
• 마지막으로 루트 노드를 방문합니다.

A에서 시작해 후위 순회 규칙을 따라가면, 가장 먼저 왼쪽 서브트리인 B를 방문하게 됩니다. B 역시 동일한 후위 순회 방식으로 탐색되며, 이 과정은 모든 노드를 방문할 때까지 반복됩니다. 위 트리를 후위 순회한 결과는 다음과 같습니다.

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

후위 순회 알고리즘

이번에 구현할 알고리즘은 다음 세 단계로 구성됩니다.

• 왼쪽 서브트리를 재귀적으로 순회합니다.
• 오른쪽 서브트리를 재귀적으로 순회합니다.
• 노드의 데이터를 출력(방문)합니다.

그럼 이 알고리즘을 클래스 내부에서 어떻게 구현하는지 살펴보겠습니다.

클래스 구현

클래스에는 단순히 루트 노드를 인자로 넘겨주는 postOrder() 메서드를 정의합니다.

postOrder() {
    postOrderHelper(this.root);
}

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

헬퍼 함수 예제

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

노드가 null이 아닌 경우 왼쪽 자식, 오른쪽 자식 순으로 재귀 호출을 진행한 뒤, 마지막에 현재 노드의 데이터를 출력하는 것을 확인할 수 있습니다.

동작 테스트

다음 코드로 직접 테스트해 볼 수 있습니다.

예제

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

실행 결과

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

3
7
5
12
50
15
10

출력 결과를 보면 가장 깊은 위치의 왼쪽 리프 노드인 3부터 시작해, 왼쪽 서브트리 전체가 먼저 처리된 후 오른쪽 서브트리가 처리되고, 최종적으로 루트 노드인 10이 마지막에 출력되는 것을 확인할 수 있습니다. 이것이 바로 후위 순회의 핵심 특징입니다.