스택으로 구현하는 C++ 이진 트리 후위 순회(비재귀) 프로그램

이진 트리를 후위 순회(post-order)하면 가장 먼저 왼쪽 서브트리를 방문하고, 그다음 오른쪽 서브트리를 방문한 뒤 마지막에 루트(root)를 방문합니다. 이 글에서는 재귀 호출 없이 스택(stack) 자료구조만을 사용해 이진 트리를 후위 순회하는 C++ 프로그램을 소개합니다.

후위 순회의 동작 원리

후위 순회는 노드의 값을 처리하는 시점이 왼쪽과 오른쪽 자식 노드를 모두 방문한 후라는 점이 특징입니다. 재귀 함수를 사용하지 않고 구현하려면, 각 노드가 몇 번째로 스택에서 처리되는지를 추적할 수 있는 별도의 플래그 변수(v)를 두어 자식 노드 방문 여부를 관리해야 합니다.

알고리즘

후위 순회 절차는 다음과 같습니다.

Begin
    postorder_traversal(struct node*t, struct tree**top) 선언
        if(t==NULL) then
            "Empty Tree" 출력
            Return
        "Postorder Data Using Stack :" 출력
        push(t,top) 함수를 호출하여 값 삽입
        tree 구조체 포인터 store 선언
            struct tree*store=NULL 로 초기화
        while(t!=NULL)
            store=*top
            if(store->v==0) then
                if(t->r!=NULL) then
                    (store->v)++
                    push(t->r,top)
                if(t->l!=NULL) then
                    (store->v)++
                    push(t->l,top)
                if(store->v==0) then
                    t->d 출력
                    t=NULL
                    pop(top)
            else
                t->d 출력
                t=NULL
                pop(top)
            if(*top!=NULL) then
                t=(*top)->link
End

C++ 예제 코드

아래 코드는 노드 생성 함수, 스택의 push/pop 함수, 그리고 비재귀 방식의 후위 순회 함수로 구성되어 있습니다.

#include<iostream>
#include<stdlib.h>
using namespace std;
struct node {
    int d;
    struct node *l,*r;
};
struct tree {
    int v;
    struct node*link;
    struct tree*n;
};
struct node*create_node(int);
struct node*create_node(int value) {
    struct node*new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node!=NULL) {
        new_node->d=value;
        new_node->l=new_node->r=NULL;
        return new_node;
    } else {
        printf("\n Memory overflow.");
        return NULL;
    }
}
void push(struct node*,struct tree*);
void push(struct node*node,struct tree**top) {
    struct tree*new_node=(struct tree*)malloc(sizeof(struct tree));
    if(new_node!=NULL) {
        new_node->link=node;
        new_node->n=*top;
        new_node->v=0;
        *top=new_node;
    } else {
        cout<<"\n Memory overflow.";
        return ;
    }
}
void pop(struct tree**);
void pop(struct tree**top) {
    if(*top!=NULL) {
        struct tree*remove=*top;
        *top=(*top)->n;
        remove->link=NULL;
        remove->n=NULL;
        remove=NULL;
    }
}
void postorder_traversal(struct node*,struct tree**);
void postorder_traversal(struct node*t,struct tree**top) {
    if(t==NULL) {
        cout<<"\n Empty Tree";
        return;
    }
    cout<<"\n Postorder Data Using Stack :";
    push(t,top);
    struct tree*store=NULL;
    while(t!=NULL) {
        store=*top;
        if(store->v==0) {
            if(t->r!=NULL) {
                (store->v)++;
                push(t->r,top);
            }
            if(t->l!=NULL) {
                (store->v)++;
                push(t->l,top);
            }
            if(store->v==0) {
                cout<<t->d;
                t=NULL;
                pop(top);
            }
        }
        else {
            cout<<t->d;
            t=NULL;
            pop(top);
        }
        if(*top!=NULL)
            t=(*top)->link;
    }
}
int main(){
    struct node*root=NULL;
    struct tree*top=NULL;
    root = create_node(20);
    root->l = create_node(10);
    root->r = create_node(30);
    root->r->r = create_node(7);
    root->l->l = create_node(25);
    root->l->r = create_node(35);
    root->l->r->r = create_node(40);
    root->l->l->r = create_node(26);
    postorder_traversal(root,&top);
    return 0;
}

핵심 코드 해설

1. create_node() — 노드 생성

malloc으로 새 노드의 메모리를 할당하고, 전달받은 값을 저장한 뒤 좌우 자식 포인터를 NULL로 초기화합니다. 메모리 할당에 실패하면 "Memory overflow" 메시지를 출력하고 NULL을 반환합니다.

2. push() / pop() — 스택 연산

push()는 트리 노드와 연결 정보(link) 및 방문 카운트 변수(v=0)를 함께 저장하는 스택 요소를 생성해 최상단에 추가합니다. pop()은 최상단 요소를 제거하고 해당 요소의 내부 포인터를 정리합니다.

3. postorder_traversal() — 비재귀 후위 순회

루트를 먼저 스택에 넣은 뒤 반복문을 수행합니다. 현재 노드의 자식이 존재하면 방문 카운트(v)를 증가시키며 오른쪽, 왼쪽 순서로 자식을 스택에 push합니다. 왼쪽을 나중에 push하므로 스택의 LIFO(Last In First Out) 특성에 따라 왼쪽 서브트리가 먼저 처리됩니다. 자식이 없는 노드는 즉시 값을 출력하고 pop하며, 이미 한 번 처리된 노드(v != 0)도 출력 후 pop하여 후위 순회 순서를 완성합니다.

실행 결과

Postorder Data Using Stack :26 25 40 35 10 7 30 20

출력 결과를 보면 각 노드가 왼쪽 자식 → 오른쪽 자식 → 부모 순서로 방문되었음을 확인할 수 있습니다. 이처럼 스택과 방문 카운트 변수만 활용하면 재귀 호출 없이도 후위 순회를 안정적으로 구현할 수 있습니다.