이 글에서는 이진 탐색 트리(Binary Search Tree)에 저장된 모든 키를 체계적으로 방문하는 네 가지 대표적인 순회(Traversal) 알고리즘을 살펴봅니다. 바로 중위 순회(Inorder Traversal), 전위 순회(Preorder Traversal), 후위 순회(Postorder Traversal), 그리고 레벨 순서 순회(Level-order Traversal)입니다.
설명을 위해 다음과 같은 이진 탐색 트리가 있다고 가정하겠습니다.
네 가지 순회 방식과 결과 비교
1. 중위 순회 (Inorder Traversal): 왼쪽 → 루트 → 오른쪽
중위 순회는 왼쪽 서브트리를 먼저 방문하고, 그다음 현재 노드(루트), 마지막으로 오른쪽 서브트리를 방문합니다. 이진 탐색 트리에서 중위 순회를 수행하면 키가 항상 오름차순으로 정렬되어 출력된다는 특징이 있습니다.
순회 결과: 5 8 10 15 16 20 23
2. 전위 순회 (Preorder Traversal): 루트 → 왼쪽 → 오른쪽
전위 순회는 현재 노드를 가장 먼저 출력한 뒤, 왼쪽 서브트리와 오른쪽 서브트리를 차례로 방문합니다. 트리를 복사하거나 트리의 구조를 그대로 파일에 저장할 때 유용하게 사용됩니다.
순회 결과: 10 5 8 16 15 20 23
3. 후위 순회 (Postorder Traversal): 왼쪽 → 오른쪽 → 루트
후위 순회는 왼쪽과 오른쪽 서브트리를 모두 방문한 후에야 현재 노드를 출력합니다. 자식 노드를 먼저 처리해야 하는 작업, 예를 들어 트리 삭제나 디렉터리 용량 계산 등에 활용됩니다.
순회 결과: 8 5 15 23 20 16 10
4. 레벨 순서 순회 (Level-order Traversal): 위에서 아래로, 좌에서 우로
레벨 순서 순회는 루트부터 시작해 깊이가 같은 노드들을 한 층씩 방문하는 방식으로, 너비 우선 탐색(BFS)이라고도 부릅니다. 앞의 세 가지 순회가 재귀 호출(스택) 기반인 것과 달리, 큐(Queue) 자료구조를 사용해 구현한다는 점이 특징입니다.
순회 결과: 10, 5, 16, 8, 15, 20, 23
알고리즘 (의사코드)
[중위 순회]
inorderTraverse(root):
시작
만약 root가 비어 있지 않으면
inorderTraversal(root의 왼쪽 자식)
root의 값 출력
inorderTraversal(root의 오른쪽 자식)
end if
종료
[전위 순회]
preorderTraverse(root):
시작
만약 root가 비어 있지 않으면
root의 값 출력
preorderTraversal(root의 왼쪽 자식)
preorderTraversal(root의 오른쪽 자식)
end if
종료
[후위 순회]
postorderTraverse(root):
시작
만약 root가 비어 있지 않으면
postorderTraversal(root의 왼쪽 자식)
postorderTraversal(root의 오른쪽 자식)
root의 값 출력
end if
종료
[레벨 순서 순회]
levelOrderTraverse(root):
시작
노드를 저장할 큐 que 정의
root를 que에 삽입
que가 비어 있지 않은 동안 반복
item := que의 맨 앞에 있는 노드
item의 값 출력
만약 item의 왼쪽 자식이 null이 아니면
item의 왼쪽 자식을 que에 삽입
end if
만약 item의 오른쪽 자식이 null이 아니면
item의 오른쪽 자식을 que에 삽입
end if
que에서 맨 앞 요소 삭제
done
종료
C++ 구현 예제
아래는 네 가지 순회를 모두 구현한 C++ 코드입니다. 먼저 7개의 키(10, 5, 16, 20, 15, 8, 23)를 이진 탐색 트리에 삽입한 뒤, 각 순회 함수를 호출해 결과를 확인합니다.
#include<iostream>
#include<queue>
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; // 시작 시 루트를 NULL로 초기화
}
void inorder_traversal(node *r);
void preorder_traversal(node *r);
void postorder_traversal(node *r);
void levelorder_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; // 주어진 키 값을 노드에 저장
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::inorder_traversal(node *r){
if(r != NULL){ // 왼쪽 → 루트 → 오른쪽 순서로 방문
inorder_traversal(r->left);
cout << r->value << " ";
inorder_traversal(r->right);
}
}
void tree::preorder_traversal(node *r){
if(r != NULL){ // 루트 → 왼쪽 → 오른쪽 순서로 방문
cout << r->value << " ";
preorder_traversal(r->left);
preorder_traversal(r->right);
}
}
void tree::postorder_traversal(node *r){
if(r != NULL){ // 왼쪽 → 오른쪽 → 루트 순서로 방문
postorder_traversal(r->left);
postorder_traversal(r->right);
cout << r->value << " ";
}
}
void tree::levelorder_traversal(node *root){
queue <node*> que;
node *item;
que.push(root); // 가장 먼저 루트를 큐에 삽입
while(!que.empty()){
item = que.front(); // 큐의 맨 앞 요소를 가져옴
cout << item->value << " ";
if(item->left != NULL) // 왼쪽 자식이 있으면 큐에 삽입
que.push(item->left);
if(item->right != NULL) // 오른쪽 자식이 있으면 큐에 삽입
que.push(item->right);
que.pop(); // 처리가 끝난 요소를 큐에서 제거
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL){
return (get_node(key)); // 트리가 비어 있으면 새 노드를 루트로 생성
}
if(key < root->value){ // 키가 루트 값보다 작으면 왼쪽으로 이동
root->left = insert_node(root->left, key);
}else if(key > root->value){ // 키가 루트 값보다 크면 오른쪽으로 이동
root->right = insert_node(root->right, key);
}
return root; // 키가 이미 존재하면 다시 삽입하지 않음
}
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 << "In-Order Traversal: ";
my_tree.inorder_traversal(my_tree.root);
cout << "\nPre-Order Traversal: ";
my_tree.preorder_traversal(my_tree.root);
cout << "\nPost-Order Traversal: ";
my_tree.postorder_traversal(my_tree.root);
cout << "\nLevel-Order Traversal: ";
my_tree.levelorder_traversal(my_tree.root);
}
실행 결과
In-Order Traversal: 5 8 10 15 16 20 23 Pre-Order Traversal: 10 5 8 16 15 20 23 Post-Order Traversal: 8 5 15 23 20 16 10 Level-Order Traversal: 10 5 16 8 15 20 23
정리
중위·전위·후위 순회는 모두 재귀 호출을 이용한 깊이 우선 방식이며, 세 연산(출력, 왼쪽 방문, 오른쪽 방문)의 실행 순서만 다릅니다. 반면 레벨 순서 순회는 큐를 사용하는 너비 우선 방식으로, 트리를 층별로 탐색해야 할 때 적합합니다. 각 순회 방식의 특성을 이해하고 목적에 맞게 선택하면 효율적인 트리 처리가 가능합니다.