데이터 구조에서 후위 순회(Post-order Traversal) 완벽 이해하기

이 글에서는 이진 탐색 트리(Binary Search Tree)에서 사용되는 후위 순회(Post-order Traversal) 기법을 재귀(Recursive) 방식으로 구현하는 방법을 자세히 살펴보겠습니다.

후위 순회는 '왼쪽 서브트리 → 오른쪽 서브트리 → 루트' 순서로 노드를 방문하는 트리 순회 방식입니다. 트리를 삭제하거나, 자식 노드를 먼저 처리한 후 부모 노드를 처리해야 하는 상황에서 특히 유용합니다.

예시 트리

다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.

이 트리를 후위 순회로 방문하면 다음과 같은 순서로 노드가 출력됩니다.

순회 결과: 8 → 5 → 15 → 23 → 20 → 16 → 10

알고리즘

후위 순회의 핵심 로직은 매우 간단합니다. 현재 노드가 존재하는지 확인한 뒤, 왼쪽 서브트리와 오른쪽 서브트리를 먼저 재귀적으로 순회하고 마지막에 현재 노드의 값을 출력합니다.

postorderTraverse(root):
Begin
    if root is not empty, then
        postorderTraversal(left of root)
        postorderTraversal(right of root)
        print the value of root
    end if
End

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. 노드 생성, 삽입, 후위 순회 기능을 클래스 단위로 깔끔하게 분리했습니다.

#include<iostream>
using namespace std;
class node{
    public:
        int h_left, h_right, bf, value;
        node *left, *right;
};
class tree{
    private:
        node *get_node(int key);
    public:
        node *root;
        tree(){
            root = NULL; // 시작 시 루트를 NULL로 초기화
        }
        void postorder_traversal(node *r);
        node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
    node *new_node;
    new_node = new node; // 새 노드를 동적으로 생성
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key; // 전달받은 key 값을 저장
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}
void tree::postorder_traversal(node *r){
    if(r != NULL){ // 노드가 존재하면 왼쪽 - 오른쪽 - 루트 순으로 방문
        postorder_traversal(r->left);
        postorder_traversal(r->right);
        cout << r->value << " ";
    }
}
node *tree::insert_node(node *root, int key){
    if(root == NULL){
        return (get_node(key)); // 트리가 비어 있으면 새 노드를 루트로 생성
    }
    if(key < root->value){ // key가 루트 값보다 작으면 왼쪽으로 이동
        root->left = insert_node(root->left, key);
    }else if(key > root->value){ // key가 루트 값보다 크면 오른쪽으로 이동
        root->right = insert_node(root->right, key);
    }
    return root; // key가 이미 존재하면 중복 삽입하지 않음
}
main(){
    node *root;
    tree my_tree;
    // 트리에 여러 키 값을 삽입
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "Post-Order Traversal: ";
    my_tree.postorder_traversal(my_tree.root);
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.

Post-Order Traversal: 8 5 15 23 20 16 10

정리

후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 모두 방문한 후에야 루트 노드를 처리한다는 점에서 중위 순회(In-order)나 전위 순회(Pre-order)와 차별화됩니다. 이러한 특성 덕분에 트리 삭제 연산이나 디렉터리 용량 계산처럼 자식 노드의 결과가 필요한 작업에서 널리 활용됩니다. 재귀 호출 구조만 이해하면 구현 자체는 매우 직관적이므로, 위 예제 코드를 직접 실행해 보며 동작 원리를 익혀보시기 바랍니다.