【C++】二分探索木から奇数の値を持つノードをすべて出力する方法

この記事では、二分探索木（BST）が与えられたときに、奇数の値を持つすべてのノードを出力する方法を解説します。

二分探索木とは

二分探索木は、以下の性質を持つ特殊な木構造です。

• 左部分木には、必ずルートノードより小さい値が格納される
• 右部分木には、必ずルートノードより大きい値が格納される
• 左右どちらの部分木も、上記の2つの性質を満たす必要がある

具体例を見て、問題を確認してみましょう。

入力となる二分探索木：

出力： 1 3 9

解法のアプローチ

この問題を解く最もシンプルな方法は、木全体を走査することです。走査の過程で各ノードの値をチェックし、その値が奇数であれば出力し、偶数であれば何もせず次のノードへ進みます。

プログラムの計算量はノードの総数に依存します。すべてのノードを一度ずつ訪問するため、時間計算量は O(n) となります。

実装のポイント

今回のコードでは中順走査（inorder traversal）を使用しています。中順走査は「左部分木 → ルート → 右部分木」の順で訪問するため、二分探索木の場合、値が昇順に処理されるという利点があります。そのため、出力結果も昇順（1 3 9）になっています。

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<<"Nodes with odd values are :\n";
    printOddNodes(root);
    return 0;
}

実行結果

Nodes with odd values are −
1 3 9

まとめ

二分探索木から奇数のノードを取り出すには、再帰的な中順走査を行いながら各ノードの値を判定するだけで実現できます。アルゴリズムは非常にシンプルですが、木構造の走査と条件分岐の基本的な組み合わせを学ぶのに適した例題です。同様の手法を応用すれば、「偶数のみ」「特定の範囲内の値のみ」といった出力にも簡単に拡張できます。