C++로 이진 탐색 트리의 홀수 노드 모두 출력하기

이 문제에서는 하나의 이진 탐색 트리(Binary Search Tree)가 주어지며, 우리의 목표는 값이 홀수인 모든 노드를 찾아 출력하는 것입니다.

이진 탐색 트리란?

이진 탐색 트리는 다음과 같은 특성을 가진 특수한 형태의 트리 자료구조입니다.

• 왼쪽 서브트리에는 항상 루트 노드보다 작은 값들이 위치합니다.
• 오른쪽 서브트리에는 항상 루트 노드보다 큰 값들이 위치합니다.
• 왼쪽과 오른쪽 서브트리 역시 위 두 가지 성질을 재귀적으로 만족해야 합니다.

문제 이해를 위한 예시

예를 들어 다음과 같은 이진 탐색 트리가 주어졌다고 가정해 보겠습니다.

출력 결과: 1 3 9

이처럼 트리 전체를 순회하면서 홀수 값(1, 3, 9)만 골라 출력하면 됩니다.

접근 방법

이 문제를 해결하는 가장 간단한 방법은 트리 순회(Tree Traversal)입니다. 트리를 순회하면서 각 노드의 값을 확인하고, 해당 값이 홀수라면 출력하고 짝수라면 다음 노드로 이동하면 됩니다.

순회 방식으로는 중위 순회(Inorder Traversal)를 사용하면 이진 탐색 트리의 특성 덕분에 오름차순으로 정렬된 결과를 얻을 수 있다는 장점도 있습니다.

프로그램의 복잡도는 트리에 포함된 노드의 개수에 비례합니다.
시간 복잡도: O(n)

C++ 구현 예제

아래 프로그램은 위에서 설명한 해결 방법을 구현한 코드입니다.

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

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

Node* newNode(int item){
    Node* temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

Node* insertNode(Node* node, int key){
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insertNode(node->left, key);
    else
        node->right = insertNode(node->right, key);
    return node;
}

void printOddNodes(Node* root){
    if (root != NULL) {
        printOddNodes(root->left);
        if (root->key % 2 != 0)
            cout << root->key << "\t";
        printOddNodes(root->right);
    }
}

int main(){
    Node* root = NULL;
    root = insertNode(root, 6);
    root = insertNode(root, 3);
    root = insertNode(root, 1);
    root = insertNode(root, 4);
    root = insertNode(root, 9);
    root = insertNode(root, 8);
    root = insertNode(root, 10);

    cout << "홀수 값을 가진 노드들 :\n";
    printOddNodes(root);
    return 0;
}

실행 결과

홀수 값을 가진 노드들 :
1	3	9

코드 설명

printOddNodes 함수는 재귀적으로 동작하는 중위 순회 방식을 사용합니다. 먼저 왼쪽 서브트리를 방문한 뒤, 현재 노드의 값이 홀수인지 검사(key % 2 != 0)하여 홀수라면 출력하고, 마지막으로 오른쪽 서브트리를 방문합니다. 이 과정을 통해 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이 됩니다.