길리랩blog

트리 순회 방식과 재귀·반복 구현 선택

전위·중위·후위 트리 순회의 방문 순서와 BST 정렬성, 식 트리 평가, 재귀 및 스택 기반 반복 구현의 선택 기준을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

루트 처리 시점이 순회의 역할을 나눈다

트리 순회(Tree Traversal)는 비선형 자료구조인 트리의 모든 노드를 정해진 규칙에 따라 중복 없이 한 번씩 방문하는 알고리즘 집합이다. 식 트리 평가, AST 처리, BST 정렬 출력처럼 방문 순서 자체가 결과에 영향을 주는 문제에서 기본 도구가 된다.

깊이 우선 순회(DFS)는 루트 노드를 언제 처리하는지에 따라 나뉜다.

  • 전위순회(Preorder): 루트 → 왼쪽 → 오른쪽
  • 중위순회(Inorder): 왼쪽 → 루트 → 오른쪽
  • 후위순회(Postorder): 왼쪽 → 오른쪽 → 루트

이진 탐색 트리(BST)를 중위순회하면 정렬된 결과를 얻을 수 있다. 시간 복잡도는 O(n)이며, 추가 공간은 평균 O(h)이다. 여기서 h는 트리 높이다.

방문 순서에 따른 선택 기준

전위순회는 루트를 가장 먼저 다룬다. 트리 구조를 직렬화하거나 AST의 전위 표기법을 만들 때 적합하다.

중위순회는 루트를 왼쪽과 오른쪽 서브트리 사이에서 처리한다. BST의 키를 오름차순으로 출력해야 할 때 이 성질을 활용할 수 있다.

후위순회는 루트를 마지막에 처리한다. 좌우 하위 트리의 계산 결과를 먼저 확보해야 하는 식 트리 평가 같은 경우에 맞는다.

방법 루트 처리 위치 성능(시간) 확장성(반복 구현) 일관성(결과 특성) 안정성(스택 위험) 운영 편의
전위(Preorder) 먼저 O(n) 쉬움(스택 1개) 구조 직렬화 용이 재귀 시 편향 트리 위험 구현·디버깅 용이
중위(Inorder) 가운데 O(n) 쉬움(스택 1개) BST 정렬 출력 재귀 시 편향 트리 위험 빈번한 실무 활용
후위(Postorder) 마지막 O(n) 보통(스택+마커/lastVisited) 하위 결과 선행 보장 재귀 시 편향 트리 위험 식 평가에 최적

예시 트리에서 확인하는 출력 순서

⤢✕ABCDEF
  • Preorder: A B D E C F
  • Inorder: D B E A C F
  • Postorder: D E B F C A

재귀 호출과 명시적 스택의 차이

재귀 구현은 정의를 코드에 그대로 옮길 수 있어 간결하다. 호출 스택을 이용하므로 구현 편의성도 높다.

반복 구현은 명시적 스택과 방문 플래그를 사용해 호출 스택 의존성을 피한다. 대형 트리나 한쪽으로 치우친 트리에서는 반복 구현이 안정성 측면에서 유리하다. 편향 트리는 높이≈n이 될 수 있으므로 재귀 호출의 스택 오버플로 위험이 있으며, 꼬리 재귀 최적화 가능 여부도 언어에 따라 점검해야 한다.

빈 트리(null 루트)와 좌우 자식의 null 분기는 어느 방식이든 처리해야 한다. 일반 트리(k-ary)로 확장할 때는 자식 방문 순서를 명시해야 하며, 계층 중심 처리가 필요하면 레벨순회(BFS)를 함께 사용할 수 있다.

스택으로 중위순회를 진행하는 흐름

반복 Inorder는 현재 노드를 왼쪽 끝까지 스택에 넣은 뒤, 하나를 꺼내 방문하고 오른쪽 서브트리로 이동하는 방식으로 진행한다.

  1. 현재 포인터 curr = root, 보조 스택 stack = []를 초기화한다.
  2. curr를 왼쪽으로 끝까지 이동하며 push한다.
  3. 스택에서 pop한 노드를 방문(출력)한 뒤 오른쪽으로 한 칸 이동한다.
  4. curr 또는 stack이 존재하는 동안 위 과정을 반복한다.

출력은 방문 순서 스트림이다. root == null이면 즉시 종료하며, 메모리 제약이 있거나 편향 트리의 최대 스택 크기≈높이 h를 고려해야 하면 재귀 대신 반복 구현을 택한다.

Python 구현

전제조건은 Python 3.11+와 표준 라이브러리이며, 노드는 좌우 자식 포인터를 가진 이진 트리로 둔다.

재귀 방식은 각 순회의 루트 처리 위치를 가장 직접적으로 보여 준다.

# Python 3.11+
from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: str
    left: Optional["Node"] = None
    right: Optional["Node"] = None

def preorder(n: Optional[Node]) -> None:
    if not n: return
    print(n.val, end=" ")
    preorder(n.left)
    preorder(n.right)

def inorder(n: Optional[Node]) -> None:
    if not n: return
    inorder(n.left)
    print(n.val, end=" ")
    inorder(n.right)

def postorder(n: Optional[Node]) -> None:
    if not n: return
    postorder(n.left)
    postorder(n.right)
    print(n.val, end=" ")

# 예시 트리
#       A
#      / \
#     B   C
#    / \   \
#   D   E   F
A = Node("A",
        left=Node("B", Node("D"), Node("E")),
        right=Node("C", None, Node("F")))

preorder(A);  print()  # A B D E C F
inorder(A);   print()  # D B E A C F
postorder(A); print()  # D E B F C A

반복 방식에서는 Inorder에 스택을 사용하고, Postorder에서는 마커/lastVisited로 이미 처리한 오른쪽 자식을 구분한다.

def inorder_iter(root: Optional[Node]) -> None:
    stack, curr = [], root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        print(curr.val, end=" ")
        curr = curr.right

def postorder_iter(root: Optional[Node]) -> None:
    stack, last, curr = [], None, root
    while curr or stack:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            peek = stack[-1]
            if peek.right and last is not peek.right:
                curr = peek.right
            else:
                print(peek.val, end=" ")
                last = stack.pop()

def preorder_iter(root: Optional[Node]) -> None:
    if not root: return
    stack = [root]
    while stack:
        n = stack.pop()
        print(n.val, end=" ")
        if n.right: stack.append(n.right)
        if n.left:  stack.append(n.left)

# 실행
preorder_iter(A);  print()
inorder_iter(A);   print()
postorder_iter(A); print()

Inorder에서는 왼쪽이 null이거나 이미 방문한 경우 루트를 출력한다. Postorder에서는 왼쪽과 오른쪽이 null이거나 이미 방문한 경우 루트를 출력한다.

순회 특성을 연결할 수 있는 문제

식 트리는 후위순회로 좌우 서브트리 값을 계산한 후 연산자를 적용할 수 있다. 컴파일러나 인터프리터의 AST에서는 전위순회로 노드를 전처리해 심볼을 수집하고, 후위순회로 코드를 생성한다.

BST 데이터 덤프와 범위 질의에서는 중위순회를 이용해 정렬된 값을 출력하고, 범위 조건(L ≤ key ≤ R)을 필터링할 수 있다. 파일시스템이나 구성 트리를 탐색할 때는 전위순회로 디렉터리를 생성하고, 후위순회로 정리·삭제 순서를 보장한다.

시간 복잡도 O(n)은 입력 크기에 선형으로 확장되며, 추가 공간 O(h)은 메모리 사용 상한을 예측하게 한다. 반복화하면 재귀 프레임을 제거해 수십만~수백만 노드 규모의 대형 트리에서 스택 오버플로 리스크가 0에 수렴한다. 방문 결과의 일관성은 디버깅과 테스트를 수월하게 하고, 평가·직렬화·정렬이라는 문제 성격에 맞는 순서를 고르면 구현도 단순해진다.

트리 순회알고리즘DFS이진 트리자료구조