C++로 구현하는 이진 트리의 반시계 방향 나선형 순회

이진 트리의 반시계 방향 나선형 순회(Anti-Clockwise Spiral Traversal)란 트리의 노드들을 나선 모양으로 방문하되, 일반적인 시계 방향과는 반대 순서로 탐색하는 기법입니다. 즉, 최상위 레벨부터 시작해 레벨을 번갈아 가며 오른쪽→왼쪽, 왼쪽→오른쪽 방향을 교차하며 노드를 출력합니다.

반시계 방향 나선형 순회의 동작 원리

아래 그림은 이진 트리가 반시계 방향 나선형으로 순회되는 과정을 보여줍니다.

알고리즘 설명

나선형 순회를 위한 알고리즘은 다음과 같은 방식으로 동작합니다.

두 개의 변수 i와 j를 선언하고, 각각 i = 1(최상위 레벨)과 j = 트리의 높이(최하위 레벨)로 초기화합니다.
현재 출력할 방향(구간)을 결정하기 위한 플래그(flag) 변수를 사용하며, 초기값은 false(0)로 설정합니다.
i <= j 조건을 만족하는 동안 루프를 반복합니다.
플래그가 0이면 i번째 레벨을 오른쪽에서 왼쪽으로 출력하고 i를 증가시킨 뒤 플래그를 반전합니다.
플래그가 1이면 j번째 레벨을 왼쪽에서 오른쪽으로 출력하고 j를 감소시킨 뒤 플래그를 다시 반전합니다.

이 과정은 이진 트리의 모든 노드가 출력될 때까지 계속됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Node {
   struct Node* left;
   struct Node* right;
   int data;
   Node(int data) {
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
// 트리의 높이를 재귀적으로 계산하는 함수
int height(struct Node* root) {
   if (root == NULL)
      return 0;
   int lheight = height(root->left);
   int rheight = height(root->right);
   return max(1 + lheight, 1 + rheight);
}
// 특정 레벨을 왼쪽에서 오른쪽으로 출력하는 함수
void leftToRight(struct Node* root, int level) {
   if (root == NULL)
      return;
   if (level == 1)
      cout << root->data << " ";
   else if (level > 1) {
      leftToRight(root->left, level - 1);
      leftToRight(root->right, level - 1);
   }
}
// 특정 레벨을 오른쪽에서 왼쪽으로 출력하는 함수
void rightToLeft(struct Node* root, int level) {
   if (root == NULL)
      return;
   if (level == 1)
      cout << root->data << " ";
   else if (level > 1) {
      rightToLeft(root->right, level - 1);
      rightToLeft(root->left, level - 1);
   }
}
int main() {
   // 예제 이진 트리 생성
   struct Node* root = new Node(1);
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->right->left = new Node(5);
   root->right->right = new Node(7);
   root->left->left->left = new Node(10);
   root->left->left->right = new Node(11);
   root->right->right->left = new Node(8);
   int i = 1;
   int j = height(root);
   int flag = 0;
   // 나선형 순회 수행
   while (i <= j) {
      if (flag == 0) {
         rightToLeft(root, i);
         flag = 1;
         i++;
      } else {
         leftToRight(root, j);
         flag = 0;
         j--;
      }
   }
   return 0;
}

실행 결과

1 10 11 8 3 2 4 5 7

동작 과정 상세 분석

위 코드의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.

레벨 1 (오른쪽→왼쪽): 루트 노드 1 출력
레벨 4 (왼쪽→오른쪽): 최하위 레벨의 10 11 8 출력
레벨 2 (오른쪽→왼쪽): 3 2 출력
레벨 3 (왼쪽→오른쪽): 4 5 7 출력

이처럼 양 끝 레벨부터 안쪽으로 이동하며 방향을 번갈아 전환하는 것이 반시계 방향 나선형 순회의 핵심입니다. 이 알고리즘의 시간 복잡도는 O(n²)이며, 여기서 n은 트리의 노드 개수입니다. 각 레벨마다 루트부터 해당 레벨까지 재귀적으로 내려가기 때문입니다. 큐 두 개를 활용하면 O(n)으로 최적화할 수 있습니다.