이 글에서는 이진 탐색 트리(Binary Search Tree)를 레벨 순서(level-order)로 순회하는 방법을 살펴보겠습니다. 레벨 순서 순회는 루트 노드부터 시작해 같은 깊이(레벨)에 있는 노드들을 왼쪽에서 오른쪽으로 차례대로 방문한 뒤, 한 단계 아래 레벨로 내려가는 방식입니다. 너비 우선 탐색(BFS, Breadth-First Search)과 같은 개념으로, 큐(queue) 자료구조를 활용해 손쉽게 구현할 수 있습니다.
레벨 순서 순회의 동작 원리
예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.
루트 10에서 출발해 각 레벨을 순서대로 방문하면 순회 결과는 다음과 같습니다.
순회 순서: 10 → 5 → 16 → 8 → 15 → 20 → 23
- 레벨 0: 10
- 레벨 1: 5, 16
- 레벨 2: 8, 15, 20, 23
알고리즘
레벨 순서 순회는 큐를 이용해 다음 절차로 수행됩니다.
levelOrderTraverse(root):
Begin
define queue que to store nodes
insert root into the que.
while que is not empty, do
item := item present at front position of queue
print the value of item
if left of the item is not null, then
insert left of item into que
end if
if right of the item is not null, then
insert right of item into que
end if
delete front element from que
done
End
핵심 아이디어는 단순합니다. 방문한 노드의 자식들을 큐에 미리 넣어두면, 큐의 선입선출(FIFO) 특성 덕분에 자연스럽게 위쪽 레벨부터 아래쪽 레벨 순으로 노드를 처리할 수 있습니다. 시간 복잡도는 모든 노드를 한 번씩 방문하므로 O(n), 공간 복잡도도 최악의 경우 마지막 레벨의 노드 수만큼 저장해야 하므로 O(n)입니다.
C++ 구현 예제
#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 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::levelorder_traversal(node *root){
queue <node*> que;
node *item;
que.push(root); // 가장 먼저 루트를 큐에 삽입
while(!que.empty()){
item = que.front(); // 큐의 앞쪽(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 << "Level-Order Traversal: ";
my_tree.levelorder_traversal(my_tree.root);
}
실행 결과
Level-Order Traversal: 10 5 16 8 15 20 23
출력 결과에서 확인할 수 있듯이, 노드들이 루트부터 시작해 레벨별로 왼쪽에서 오른쪽 순서로 정확히 방문된 것을 볼 수 있습니다. 이처럼 레벨 순서 순회는 트리의 구조를 위에서 아래로, 폭넓게 탐색해야 하는 상황(예: 트리의 최소 깊이 계산, 레벨별 데이터 출력 등)에서 매우 유용하게 활용됩니다.