재귀 호출 없이 이진 트리를 중위 순회하는 C++ 프로그램

이진 트리를 중위 순회(Inorder Traversal)하면 먼저 왼쪽 서브트리를 방문하고, 그다음 루트 노드를 거쳐 마지막에 오른쪽 서브트리를 방문합니다. 특히 이진 탐색 트리(BST)에서는 중위 순회 시 키 값이 항상 오름차순으로 출력된다는 특징이 있습니다.

일반적으로 중위 순회는 재귀 함수로 간단하게 구현할 수 있지만, 이번 글에서는 재귀 호출 없이 스택(Stack) 자료구조만 사용하여 중위 순회를 수행하는 C++ 프로그램을 다룹니다. 재귀 대신 명시적인 스택을 사용하면 깊이가 매우 큰 트리에서도 스택 오버플로우 걱정 없이 안전하게 순회할 수 있다는 장점이 있습니다.

알고리즘

시작
    함수 inOrder():
        스택 s를 선언한다.
        현재 노드(current)를 루트(root)로 설정한다.
        현재 노드가 NULL이 아니거나 스택이 비어 있지 않은 동안 반복:
            현재 노드가 NULL이 아닌 동안:
                현재 노드를 스택에 push 한다.
                왼쪽 자식 노드를 현재 노드로 설정한다.
            스택의 최상단(top) 노드를 현재 노드로 지정한 뒤 pop 한다.
            현재 노드의 값을 출력한다.
            오른쪽 자식 노드를 현재 노드로 설정한다.
    루트, 왼쪽 노드, 오른쪽 노드에 요소들을 삽입하여 트리를 구성한다.
    inOrder() 함수를 호출하여 트리를 순회한다.
끝.

예제 코드

#include<bits/stdc++.h>
using namespace std;

struct n {
   int d;
   struct n* l;
   struct n* r;
   n (int d) {
      this->d = d;
      l = r = NULL;
   }
};

void inOrder(struct n *root) {
   stack<n *> s;
   n *current = root;

   while (current != NULL || s.empty() == false) {
      while (current != NULL) {
         s.push(current);
         current = current->l;
      }

      current = s.top();
      s.pop();

      cout << current->d << " ";
      current = current->r;
   }
}

int main() {
   struct n *root = new n(7);

   root->l = new n(6);
   root->r = new n(2);
   root->l->l = new n(1);
   root->l->r = new n(9);

   inOrder(root);
   return 0;
}

코드 설명

1. 노드 구조체 정의

구조체 n은 정수형 데이터 d와 왼쪽·오른쪽 자식 포인터 l, r을 가지며, 생성자를 통해 값을 초기화하고 자식 포인터를 NULL로 설정합니다.

2. inOrder() 함수 — 스택 기반 순회

먼저 내부 while 문에서 현재 노드부터 가장 왼쪽 끝 노드까지 경로상의 모든 노드를 스택에 차례대로 push 합니다. 더 이상 왼쪽 자식이 없으면 스택에서 노드를 하나 꺼내(pop) 값을 출력하고, 해당 노드의 오른쪽 서브트리로 이동하여 같은 과정을 반복합니다. 이렇게 하면 '왼쪽 → 루트 → 오른쪽' 순서가 자연스럽게 유지됩니다.

3. main() 함수 — 트리 구성

루트 노드 7을 만들고, 왼쪽 자식 6(자식으로 1과 9), 오른쪽 자식 2를 연결하여 트리를 구성한 뒤 inOrder()를 호출합니다.

실행 결과

1 6 9 7 2

출력 결과를 보면 트리의 모든 노드가 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 정확히 방문되었음을 확인할 수 있습니다.