이번 글에서는 이진 탐색 트리(Binary Search Tree)에서 널리 사용되는 전위 순회(Pre-order Traversal) 기법을 재귀(Recursive) 방식으로 구현하는 방법을 살펴보겠습니다.
전위 순회란 무엇인가?
전위 순회는 트리의 노드를 루트(Root) → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문하는 순회 방식입니다. 루트 노드를 가장 먼저 처리하기 때문에 '전위(前位)'라는 이름이 붙었으며, 트리 구조를 복제하거나 수식 트리를 접두 표기법(Prefix Notation)으로 변환할 때 특히 유용하게 활용됩니다.
다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.
이 트리를 전위 순회하면 노드의 방문 순서는 다음과 같습니다.
10 → 5 → 8 → 16 → 15 → 20 → 23
알고리즘
전위 순회의 핵심 로직은 매우 간단합니다. 현재 노드의 값을 먼저 출력한 뒤, 왼쪽 자식과 오른쪽 자식에 대해 동일한 과정을 재귀적으로 반복하면 됩니다.
preorderTraverse(root):
시작
if root가 비어 있지 않으면
root의 값을 출력
preorderTraverse(root의 왼쪽 자식)
preorderTraverse(root의 오른쪽 자식)
end if
종료C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. 노드 생성, 키 삽입, 전위 순회 기능을 클래스로 깔끔하게 캡슐화했습니다.
#include<iostream>
using namespace std;
class node{
public:
int h_left, h_right, bf, value;
node *left, *right;
};
class tree{
private:
node *get_node(int key);
public:
node *root;
tree(){
root = NULL; // 시작 시 root를 NULL로 초기화
}
void preorder_traversal(node *r);
node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
node *new_node;
new_node = new node; // 새 노드를 동적으로 생성
new_node->h_left = 0; new_node->h_right = 0;
new_node->bf = 0;
new_node->value = key; // 주어진 key 값을 노드에 저장
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::preorder_traversal(node *r){
if(r != NULL){ // 노드가 존재하면 루트 → 왼쪽 → 오른쪽 순으로 방문
cout << r->value << " ";
preorder_traversal(r->left);
preorder_traversal(r->right);
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL){
return (get_node(key)); // 트리가 비어 있으면 새 노드를 루트로 생성
}
if(key < root->value){ // key가 루트 값보다 작으면 왼쪽으로 이동
root->left = insert_node(root->left, key);
}else if(key > root->value){ // key가 루트 값보다 크면 오른쪽으로 이동
root->right = insert_node(root->right, key);
}
return root; // key가 이미 존재하면 중복 삽입하지 않음
}
main(){
node *root;
tree my_tree;
// 트리에 여러 키 값을 삽입
my_tree.root = my_tree.insert_node(my_tree.root, 10);
my_tree.root = my_tree.insert_node(my_tree.root, 5);
my_tree.root = my_tree.insert_node(my_tree.root, 16);
my_tree.root = my_tree.insert_node(my_tree.root, 20);
my_tree.root = my_tree.insert_node(my_tree.root, 15);
my_tree.root = my_tree.insert_node(my_tree.root, 8);
my_tree.root = my_tree.insert_node(my_tree.root, 23);
cout << "Pre-Order Traversal: ";
my_tree.preorder_traversal(my_tree.root);
}실행 결과
Pre-Order Traversal: 10 5 8 16 15 20 23
마무리
전위 순회는 루트를 가장 먼저 방문한다는 점에서 중위 순회(In-order)나 후위 순회(Post-order)와 뚜렷이 구별됩니다. 재귀 호출만으로 간결하게 구현할 수 있어 코딩 테스트와 실무 양쪽에서 자주 등장하는 필수 개념이므로, 위 예제 코드를 직접 실행해 보며 동작 원리를 확실히 익혀두시기 바랍니다.