이진트리 순회 (Binary Tree Traversal)

한 줄 정의: 이진트리의 모든 노드를 부모와 왼쪽·오른쪽 자식을 방문하는 순서에 따라 빠짐없이 한 번씩 방문하는 방법입니다.

쉽게 풀면

가족 계보도를 읽는 방법이 여러 가지라고 생각해봅시다. "나부터 말하고 왼쪽 형제, 오른쪽 형제 순으로 말하기"(전위 순회), "왼쪽 형제, 나, 오른쪽 형제 순으로 말하기"(중위 순회), "왼쪽 형제, 오른쪽 형제, 마지막에 나를 말하기"(후위 순회)처럼, 같은 나무 구조라도 어떤 순서로 노드를 방문하느냐에 따라 이름이 다릅니다. 전위(Preorder)는 부모→왼쪽→오른쪽, 중위(Inorder)는 왼쪽→부모→오른쪽, 후위(Postorder)는 왼쪽→오른쪽→부모 순서로 방문합니다. 특히 이진탐색트리를 중위 순회하면 값이 항상 오름차순으로 나온다는 성질이 유명합니다.

왜 중요한가

이진트리 순회는 컴파일러의 구문 분석, 데이터베이스 인덱스 탐색, 파일 시스템 구조 처리, 머신러닝의 결정 트리 해석 등 트리 형태로 데이터를 표현하는 거의 모든 분야에서 기본 연산으로 쓰입니다. 데이터를 어떤 순서로 방문하느냐가 알고리즘의 정확성과 효율성을 좌우하기 때문에, 새로운 트리 기반 자료구조나 알고리즘을 제안하는 논문에서는 전위·중위·후위 순회 중 어떤 것을 채택했는지, 그 이유는 무엇인지를 명시적으로 밝히는 경우가 많습니다. 또한 순회 방식은 시간복잡도 분석이나 병렬화 가능성을 논할 때도 출발점이 되는 개념입니다.

논문에서는 이렇게 쓰입니다

"구문 분석 트리를 중위 순회하여 원래의 수식 표현을 복원하고, 후위 순회 결과를 스택 기반 계산기의 입력으로 사용했다."

이 문장은 "트리 구조로 표현된 데이터를 특정 순서로 방문하면서 원하는 형태(수식, 계산 순서 등)로 다시 풀어냈다"는 뜻입니다. 어떤 순회 방식을 쓰느냐에 따라 같은 트리에서도 전혀 다른 순서의 결과가 나옵니다.

"학습된 결정 트리를 전위 순회하면서 각 분기 노드의 특징 중요도를 추출하여 모델의 예측 근거를 시각화했다."

머신러닝 분야에서는 학습이 끝난 결정 트리 모델을 해석하거나 시각화할 때 순회가 쓰입니다. 루트에서부터 순서대로 방문하며 어떤 조건들이 예측 결과로 이어졌는지를 사람이 읽을 수 있는 형태로 풀어내는 것입니다.

"디렉터리 구조를 이진 검색 트리로 재구성한 뒤 중위 순회를 적용해, 파일 접근 빈도에 따라 정렬된 인덱스를 생성했다."

파일 시스템이나 데이터베이스 인덱싱 연구에서는 계층 구조를 트리로 표현하고, 이를 순회해 정렬되거나 검색에 유리한 형태로 재구성하는 방식이 자주 등장합니다.

조금 더 깊게 보면

세 가지 기본 순회(전위·중위·후위) 외에도, 같은 깊이의 노드를 한 층씩 옆으로 방문하는 레벨 순서 순회(Level-order Traversal)가 있으며, 이는 보통 재귀 대신 큐(Queue) 자료구조를 이용해 구현됩니다. 순회의 시간복잡도는 일반적으로 노드 개수에 비례하지만, 공간복잡도는 트리의 높이(재귀 호출 깊이 또는 스택 크기)에 좌우되므로 균형 트리인지 편향 트리인지에 따라 실제 성능 차이가 크게 날 수 있습니다. 또한 순회 순서는 트리를 문자열이나 배열로 직렬화(serialize)하고 이를 다시 복원(deserialize)하는 과정의 기반이 되기도 합니다.

주의할 점

세 가지 순회는 보통 재귀함수로 가장 간단하게 구현되지만, 트리의 깊이가 매우 깊어지면 재귀 호출이 쌓이면서 스택 오버플로가 발생할 수 있습니다. 이런 경우에는 직접 스택 자료구조를 사용한 반복문 기반 구현으로 바꿔야 안전합니다.