C++로 이진 트리의 홀수 레벨 노드 출력하기

이진 트리가 주어졌을 때, 트리의 홀수 레벨에 있는 노드들을 모두 출력하는 프로그램을 작성해야 합니다. 여기서 이진 트리의 레벨은 루트 노드부터 1로 시작하여 n까지 증가합니다.

문제에 특별한 제약 조건이 명시되어 있지 않으므로, 재귀(recursion) 또는 반복(iteration) 방식 중 하나를 선택하여 구현할 수 있습니다.

이 글에서는 재귀적 접근 방식을 사용합니다. 프로그램은 홀수 레벨의 노드를 탐색하여 출력하는 함수를 재귀적으로 호출하고, 각 호출마다 불리언 플래그를 반전시켜 현재 레벨이 홀수인지 짝수인지 판단합니다.

위 이진 트리를 기준으로 살펴보면 다음과 같습니다.

레벨 1의 노드: 10
레벨 2의 노드: 3, 211
레벨 3의 노드: 140, 162, 100, 146

홀수 레벨인 레벨 1과 레벨 3의 노드만 출력해야 하므로, 최종 출력 결과는 10, 140, 162, 100, 146이 됩니다.

알고리즘

START
Step 1 -> 노드 구조체 정의
    struct Node
        struct node *left, *right
        int data
    End
Step 2 -> 새 노드를 생성하는 함수
    node* newnode(int data)
    node->data = data
    node->left = node->right = NULL
    return (node)
Step 3 -> 홀수 레벨 노드를 찾는 함수
    void odd(Node *root, bool ifodd = true)
    IF root == NULL
        Return
    End
    if (ifodd)
        print root->data
    End
    odd(root->left, !ifodd)
    odd(root->right, !ifodd)
Step 4 -> main() 함수에서
    Node* root = newnode(45) 로 트리 생성
    root->left = newnode(23)
    odd(root) 호출
STOP

핵심 아이디어

이 알고리즘의 핵심은 ifodd라는 불리언 변수입니다. 루트에서 호출할 때는 true로 시작하고, 자식 노드로 내려갈 때마다 !ifodd(논리 부정 값)를 전달합니다. 그러면 한 레벨씩 내려갈 때마다 홀짝 여부가 자동으로 번갈아 바뀌기 때문에, 별도의 레벨 카운터 없이도 홀수 레벨의 노드만 깔끔하게 걸러낼 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node* left, *right;
};

// 홀수 레벨의 노드를 출력하는 재귀 함수
void odd(Node *root, bool ifodd = true){
    if (root == NULL)
        return;
    if (ifodd)
        cout << root->data << " ";
    odd(root->left, !ifodd);
    odd(root->right, !ifodd);
}

// 새 노드를 생성하는 함수
Node* newnode(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int main(){
    Node* root = newnode(45);
    root->left = newnode(23);
    root->right = newnode(13);
    root->left->left = newnode(24);
    root->left->right = newnode(85);
    cout<<"\nodd nodes are ";
    odd(root);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.

odd nodes are 45 24 85

루트 노드 45(레벨 1)와 레벨 3에 해당하는 24, 85가 순서대로 출력된 것을 확인할 수 있습니다. 이처럼 재귀 호출과 불리언 플래그만으로도 트리의 높이에 관계없이 홀수 레벨의 노드를 효율적으로 추출할 수 있습니다.