트리 순회란 무엇인가?
트리 순회(Tree Traversal)는 그래프 순회의 한 형태로, 트리에 속한 모든 노드를 정확히 한 번씩 방문하거나 출력하는 과정을 의미합니다. 그중 선위 순회(Preorder Traversal)는 루트 노드를 가장 먼저 방문한 뒤, 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 순서대로 탐색하는 방식입니다. 즉, (루트 → 왼쪽 → 오른쪽) 순서로 진행됩니다.
예를 들어 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
이 트리의 선위 순회 결과는 다음과 같습니다.
5 3 2 4 8 9
이제 재귀 호출 없이 스택(stack) 자료구조만으로 선위 순회를 수행하는 C++ 프로그램을 살펴보겠습니다.
C++ 전체 코드
#include<iostream>
#include <stack>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node->right)
nodeStack.push(temp_node->right);
if (temp_node->left)
nodeStack.push(temp_node->left);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
}
실행 결과
Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9
코드 상세 설명
1. node 구조체 — 트리 노드 정의
구조체 node는 트리의 개별 노드를 나타냅니다. 이 구조체는 자기 자신과 동일한 타입인 struct node 포인터를 멤버로 포함하는 자기 참조 구조체(self-referential structure)입니다.
struct node {
int data;
struct node *left;
struct node *right;
};
2. createNode() — 새 노드 생성
createNode() 함수는 malloc을 사용해 새 노드 temp에 메모리를 할당하고, 매개변수로 전달받은 값 val을 data 필드에 저장합니다. 이후 왼쪽과 오른쪽 포인터를 NULL로 초기화한 뒤 생성된 노드를 반환합니다.
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
3. preorder() — 스택 기반 비재귀 선위 순회
preorder() 함수는 스택을 활용해 트리의 요소들을 선위 순서로 출력합니다. 먼저 루트 노드를 스택에 push한 후, 스택이 빌 때까지 반복되는 while 루프를 시작합니다. 각 반복에서는 스택 최상단(top)에 있는 노드의 데이터를 출력하고 해당 노드를 pop한 뒤, 그 노드의 오른쪽 자식과 왼쪽 자식을 차례로 스택에 push합니다.
오른쪽 자식을 먼저 넣는 이유는 스택이 LIFO(Last-In-First-Out) 구조이기 때문입니다. 오른쪽을 먼저 push하면 왼쪽 자식이 스택 상단에 위치하게 되어, (루트 → 왼쪽 → 오른쪽) 순서가 자연스럽게 유지됩니다.
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node->right)
nodeStack.push(temp_node->right);
if (temp_node->left)
nodeStack.push(temp_node->left);
}
}
4. insertNode() — 이진 탐색 트리에 값 삽입
insertNode() 함수는 주어진 값을 이진 탐색 트리의 올바른 위치에 삽입합니다. 현재 노드가 NULL이면 createNode()를 호출해 새 노드를 생성하고, 그렇지 않으면 삽입할 값과 현재 노드의 값을 비교하며 적절한 위치를 찾아 내려갑니다. 삽입할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀적으로 이동합니다.
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
5. main() — 프로그램 실행 흐름
main() 함수에서는 먼저 루트 노드를 NULL로 초기화한 뒤, 필요한 값들을 하나씩 이진 탐색 트리에 삽입합니다.
struct node *root = NULL; root = insertNode(root, 5); insertNode(root, 8); insertNode(root, 3); insertNode(root, 2); insertNode(root, 6); insertNode(root, 9); insertNode(root, 4);
마지막으로 트리의 루트 노드를 인자로 preorder() 함수를 호출하여, 트리의 모든 값이 선위 순서대로 화면에 출력됩니다.
cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);
마무리
이처럼 스택을 활용하면 재귀 호출 없이도 이진 트리를 선위 순회할 수 있습니다. 재귀 방식은 코드가 간결하지만 트리의 깊이가 매우 깊을 경우 스택 오버플로우 위험이 있습니다. 따라서 명시적인 스택을 사용하는 비재귀 순회는 메모리 관리 측면에서 안정적이며, 실무 환경에서 널리 활용되는 기법입니다.