개요
이 튜토리얼에서는 C++을 사용하여 이진 트리(binary tree)에서 주어진 두 레벨 번호 사이에 있는 모든 노드를 출력하는 프로그램을 구현하는 방법을 살펴봅니다.
문제의 정의는 다음과 같습니다. 하나의 이진 트리와 함께 낮은 레벨(low)과 높은 레벨(high)이 주어졌을 때, 해당 범위에 포함되는 레벨에 속한 모든 노드의 값을 출력해야 합니다.
접근 방법
이 문제는 큐(queue) 기반의 레벨 순회(level order traversal)를 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
각 레벨의 끝을 표시하기 위한 마커(marker) 노드를 큐에 삽입합니다. 레벨 순회를 진행하면서 마커 노드를 만나면 한 레벨이 끝났음을 의미하므로 레벨 카운터를 1 증가시킵니다. 현재 레벨이 주어진 범위(low 이상)에 속하는 경우에만 노드의 데이터를 출력하고, 현재 레벨이 high를 초과하거나 큐가 비어 있으면 순회를 종료합니다.
예제 코드
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// 지정된 레벨 사이의 노드를 출력하는 함수
void print_nodes(Node* root, int low, int high){
queue <Node *> Q;
// 마커 노드 생성
Node *marker = new Node;
int level = 1;
Q.push(root);
Q.push(marker);
while (Q.empty() == false){
Node *n = Q.front();
Q.pop();
// 레벨의 끝인지 확인
if (n == marker){
cout << endl;
level++;
if (Q.empty() == true || level > high)
break;
Q.push(marker);
continue;
}
if (level >= low)
cout << n->data << " ";
if (n->left != NULL) Q.push(n->left);
if (n->right != NULL) Q.push(n->right);
}
}
Node* create_node(int data){
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main(){
struct Node *root= create_node(20);
root->left= create_node(8);
root->right= create_node(22);
root->left->left= create_node(4);
root->left->right= create_node(12);
root->left->right->left= create_node(10);
root->left->right->right= create_node(14);
cout << "지정된 레벨 사이의 요소들 :";
print_nodes(root, 2, 3);
return 0;
}실행 결과
지정된 레벨 사이의 요소들 : 8 22 4 12
코드 설명
위 예제에서 이진 트리의 루트는 20이며, 2레벨에는 8과 22, 3레벨에는 4와 12가 존재합니다. 따라서 print_nodes(root, 2, 3)을 호출하면 2레벨부터 3레벨 사이의 노드 값들이 레벨별로 줄바꿈되어 출력됩니다.
마커 노드는 실제 데이터를 담지 않는 특수한 노드로, 큐에서 이를 만나는 순간 현재 레벨의 순회가 완료되었음을 알 수 있습니다. 이 방식 덕분에 별도의 레벨 정보를 노드마다 저장하지 않고도 현재 순회 중인 레벨을 정확하게 추적할 수 있습니다.
시간 및 공간 복잡도
이 알고리즘은 트리의 모든 노드를 최대 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 또한 큐에는 최대 한 레벨의 노드들이 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 여기서 n은 트리에 포함된 노드의 총 개수입니다.