C++로 이진 트리의 홀수 레벨만 출력하는 프로그램

C++를 활용하면 이진 트리(binary tree)를 순회하면서 홀수 번째 레벨(1, 3, 5번째 레벨)에 위치한 노드들만 골라 출력할 수 있습니다. 이 글에서는 재귀 호출로 트리의 높이를 계산하고, 각 레벨별로 노드를 방문하는 방식으로 이 문제를 해결하는 프로그램을 소개합니다.

알고리즘

프로그램의 전체적인 흐름을 의사코드(pseudocode)로 정리하면 다음과 같습니다.

시작
    nod 구조체를 선언한다.
        정수형 변수 d를 선언한다.
        struct nod를 가리키는 포인터 l을 선언한다.
        struct nod를 가리키는 포인터 r을 선언한다.
    함수 newNod(int d)를 호출한다.
    newNod(int d) 함수를 정의한다.
        struct nod 타입의 포인터 node를 선언한다.
        node = (struct nod*) malloc(sizeof(struct nod)) 로 초기화한다.
        node->d = d
        node->l = NULL
        node->r = NULL
        node를 반환한다.
    printLevel(struct nod* root, int lvl) 함수를 호출한다.
    printLevel(struct nod* root, int lvl) 함수를 정의한다.
        root == NULL 이면 return 한다.
        lvl == 1 이면 root->d 값을 출력한다.
        그렇지 않고 lvl > 1 이면
            printLevel(root->l, lvl - 1) 을 재귀 호출한다.
            printLevel(root->r, lvl - 1) 을 재귀 호출한다.
    height(struct nod* node) 함수를 호출한다.
    height(struct nod* node) 함수를 정의하여 트리의 높이를 계산한다.
        node == NULL 이면 0을 반환한다.
        아니면
            int lhght = height(node->l);
            int rhght = height(node->r);
        lhght > rhght 이면 (lhght + 1)을 반환한다.
        아니면 (rhght + 1)을 반환한다.
    printLevelOrder(struct nod* root) 함수를 정의한다.
        정수형 변수 h를 선언하고 h = height(root) 로 초기화한다.
        정수형 변수 i를 선언한다.
        for (i = 1; i <= h; i += 2) 반복하며 printLevel(root, i) 를 호출한다.
    트리에 값을 삽입한다.
    "이진 트리의 홀수 번째 레벨 순회 결과" 메시지를 출력한다.
    printLevelOrder(root) 함수를 호출한다.
종료

예제 코드

#include <iostream>
#include<stdlib.h>
using namespace std;
struct nod {
    int d;
    struct nod* l;
    struct nod* r;
};
struct nod* newNod(int d);
struct nod* newNod(int d) {
    struct nod* node = (struct nod*) malloc(sizeof(struct nod));
    node->d = d;
    node->l = NULL;
    node->r = NULL;
    return (node);
}
void printLevel(struct nod* root, int lvl);
void printLevel(struct nod* root, int lvl) {
    if (root == NULL)
       return;
    if (lvl == 1)
       printf("%d ", root->d);
    else if (lvl > 1) {
       printLevel(root->l, lvl - 1);
       printLevel(root->r, lvl - 1);
    }
}
int height(struct nod* node);
int height(struct nod* node) {
    if (node == NULL)
       return 0;
    else {
       int lhght = height(node->l);
       int rhght = height(node->r);
       if (lhght > rhght)
          return (lhght + 1);
       else
          return (rhght + 1);
    }
}
void printLevelOrder(struct nod* root) {
    int h = height(root);
    int i;
    for (i = 1; i <= h; i+=2)
       printLevel(root, i);
}
int main() {
    struct nod *root = newNod(7);
    root->l = newNod(6);
    root->r = newNod(4);
    root->l->l = newNod(3);
    root->l->r = newNod(5);
    root->r->l = newNod(2);
    root->r->r = newNod(1);
    cout<<"이진 트리의 홀수 번째 레벨 순회 결과 \n";
    printLevelOrder(root);
    return 0;
}

실행 결과

이진 트리의 홀수 번째 레벨 순회 결과
7 3 5 2 1

동작 원리

예제에서 사용한 트리는 총 세 개의 레벨로 구성되어 있습니다.

레벨 1: 7 (루트 노드)
레벨 2: 6, 4 → 출력 대상에서 제외
레벨 3: 3, 5, 2, 1

핵심은 printLevelOrder() 함수의 반복문입니다. 인덱스 i가 1부터 시작해 2씩 증가(i += 2)하기 때문에 짝수 레벨은 아예 건너뛰게 됩니다. 각 레벨에 대해 printLevel()이 재귀적으로 트리를 내려가다가 해당 레벨에 도달하면(lvl == 1) 노드 값을 출력하는 구조입니다.

참고로 이 구현은 레벨마다 트리를 위에서부터 다시 순회하므로 최악의 경우 O(n²)의 시간 복잡도를 가집니다. 트리의 크기가 클 경우에는 큐(queue)를 활용한 BFS 방식으로 성능을 개선할 수 있습니다.