이진 트리(binary tree)가 주어졌을 때, 트리의 레벨 순서 순회(level order traversal) 결과를 레벨별로 한 줄씩 출력하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.
레벨 순서 순회는 너비 우선 탐색(BFS, Breadth-First Search)이라고도 부르며, 루트가 있는 최상위 레벨부터 시작해 아래 레벨로 내려가면서 같은 레벨에 속한 노드들을 왼쪽에서 오른쪽 순서로 차례대로 방문하는 방식입니다. 일반적인 레벨 순회 출력과 달리, 이 문제에서는 각 레벨의 노드 값이 서로 다른 줄에 구분되어 나타나야 합니다.
예를 들어 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
위 이진 트리에 대한 기대 출력은 다음과 같습니다.
Level 0: 3 Level 1: 2 1 Level 2: 10 20 30
알고리즘
각 레벨을 구분해 출력하기 위해 큐(queue) 자료구조를 활용합니다. 핵심 아이디어는 반복문이 시작될 때 큐에 들어 있는 노드의 개수를 세어 두면, 그 개수만큼만 처리했을 때 현재 레벨의 모든 노드가 출력된다는 점입니다. 한 레벨의 출력이 끝나면 줄바꿈을 해 주면 됩니다.
시작
1단계 → 노드 구조체를 정의한다.
struct node
struct node *left, *right
int data
끝
2단계 → 새 노드를 생성하는 함수를 작성한다.
node* newnode(int data)
node *temp = new node
temp->data = data
temp->left = temp->right = NULL
return temp
3단계 → 레벨 순서 순회 함수를 작성한다.
void levelorder(node *root)
IF root == NULL
Return
End
queue<node *> que
que.push(root)
Loop While que.empty() == false
int count = que.size() // 현재 레벨의 노드 개수
Loop While count > 0
node *cur = que.front()
cur->data 출력
que.pop()
IF cur->left != NULL
que.push(cur->left)
End
IF cur->right != NULL
que.push(cur->right)
End
count를 1 감소
End
줄바꿈 출력 // 한 레벨이 끝났음을 의미
End
End
4단계 → main() 함수에서
node *root = newnode(3)으로 트리를 생성한다.
levelorder(root)를 호출한다.
종료
C++ 예제 코드
#include <iostream>
#include <queue>
using namespace std;
// 노드 구조체 정의
struct node {
struct node *left;
int data;
struct node *right;
};
// 레벨 순서 순회: 각 레벨을 한 줄씩 출력
void levelorder(node *root) {
if (root == NULL)
return;
queue<node *> que;
que.push(root);
while (!que.empty()) {
int count = que.size(); // 현재 레벨의 노드 개수
while (count > 0) {
node *cur = que.front();
cout << cur->data << " ";
que.pop();
if (cur->left != NULL)
que.push(cur->left);
if (cur->right != NULL)
que.push(cur->right);
count--;
}
cout << endl; // 한 레벨의 출력이 끝나면 줄바꿈
}
}
// 새 노드를 생성하는 함수
node* newnode(int data) {
node *temp = new node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main() {
// 예제 이진 트리 생성
node *root = newnode(3);
root->left = newnode(2);
root->right = newnode(1);
root->left->left = newnode(10);
root->left->right = newnode(20);
root->right->right = newnode(30);
levelorder(root);
return 0;
}
실행 결과
위 프로그램을 컴파일한 후 실행하면 다음과 같은 출력이 생성됩니다.
3 2 1 10 20 30
동작 원리
코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
- 루트 삽입: 먼저 루트 노드(3)를 큐에 넣습니다.
- 레벨 크기 확인: 큐의 크기를 count에 저장합니다. 첫 번째 반복에서 count는 1이므로 루트 하나만 출력한 뒤 줄바꿈을 합니다.
- 자식 노드 삽입: 노드를 출력하며 큐에서 제거할 때, 해당 노드의 왼쪽·오른쪽 자식이 존재하면 큐에 추가합니다.
- 반복: 다음 반복에서는 큐에 2와 1이 들어 있으므로 count는 2가 되고 "2 1"이 한 줄로 출력됩니다. 마지막으로 10, 20, 30이 "10 20 30"으로 출력됩니다.
이 방식은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 최악의 경우 큐에 모든 노드가 저장될 수 있어 공간 복잡도 역시 O(n)입니다.