개요
이 튜토리얼에서는 주어진 이진 트리(binary tree)의 홀수 레벨(odd level)에 있는 노드들을 출력하는 C++ 프로그램을 다룹니다.
여기서 루트(root) 노드의 레벨은 1로 간주하며, 그 아래 레벨은 짝수, 그다음 레벨은 다시 홀수가 됩니다. 즉, 레벨 1, 3, 5…에 위치한 노드들이 출력 대상입니다.
예를 들어, 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
위 이진 트리에서 홀수 레벨에 있는 노드는 1, 4, 5, 6입니다.
알고리즘 접근 방식
이 문제는 재귀(recursion)를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 노드를 방문할 때 현재 레벨이 홀수인지 여부를 불리언(boolean) 값으로 전달합니다.
- 자식 노드로 내려갈 때마다 이 값을 반전(
!is_odd)시켜 레벨의 홀짝 여부를 추적합니다. is_odd가 참일 경우 해당 노드의 값을 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* left, *right;
};
// 홀수 레벨의 노드 출력
void print_onodes(Node *root, bool is_odd = true){
if (root == NULL)
return;
if (is_odd)
cout << root->data << " " ;
print_onodes(root->left, !is_odd);
print_onodes(root->right, !is_odd);
}
// 새 노드 생성
struct Node* create_node(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node* root = create_node(13);
root->left = create_node(21);
root->right = create_node(43);
root->left->left = create_node(64);
root->left->right = create_node(85);
print_onodes(root);
return 0;
}출력 결과
13 64 85
코드 설명
print_onodes 함수는 트리를 깊이 우선으로 재귀 순회하며, is_odd 매개변수가 참일 때만 노드의 데이터를 출력합니다. 왼쪽과 오른쪽 자식을 호출할 때 !is_odd를 전달하기 때문에 한 레벨씩 내려갈 때마다 홀짝 여부가 자동으로 반전됩니다.
create_node 함수는 새 노드를 동적으로 할당하고 좌우 포인터를 NULL로 초기화하는 역할을 합니다.
main 함수에서는 루트가 13인 이진 트리를 구성한 뒤 출력 함수를 호출합니다. 루트(레벨 1)의 13과 레벨 3의 64, 85가 출력되므로 최종 결과는 13 64 85가 됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택이 트리의 높이(h)만큼 사용됩니다.