C++で二分探索木の偶数ノードをすべて出力する方法

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

二分探索木とは

二分探索木（BST: Binary Search Tree）は、以下の条件を満たす二分木です。

• 左側の部分木には、常に親ノードより小さい値を持つノードが含まれる。
• 右側の部分木には、常に親ノードより大きい値を持つノードが含まれる。
• すべてのノードが上記の2つのルールに従っている必要がある。

これらの性質により、二分探索木では効率的な検索・挿入・削除が可能になります。

問題の例

具体例を使って問題を理解しましょう。例えば、次のような二分探索木を考えます。

出力： 2 4 6 8

解法のアプローチ

この問題を解くための手順は非常にシンプルです。

1. 二分探索木のすべてのノードを巡回する。
2. 現在のノードの値が偶数かどうかを判定する。
3. 偶数であればそのノードを出力し、奇数であれば何もせず次へ進む。

ここでは、中順走査（In-order Traversal）を用いた再帰的な実装を採用します。中順走査を使うと、二分探索木のノードを昇順に訪問できるため、結果がソートされた形で出力されるという利点があります。

C++での実装例

以下のコードは、上記のロジックの動作を示したものです。

#include <iostream>
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 printEvenNode(Node* root){
    if (root != NULL) {
        printEvenNode(root->left);
        if (root->key % 2 == 0)
            cout<<root->key<<"\t";
        printEvenNode(root->right);
    }
}
int main(){
    Node* root = NULL;
    root = insertNode(root, 54);
    root = insertNode(root, 43);
    root = insertNode(root, 12);
    root = insertNode(root, 30);
    root = insertNode(root, 89);
    root = insertNode(root, 67);
    root = insertNode(root, 80);
    cout<<"All even nodes of the tree are :\n";
    printEvenNode(root);
    return 0;
}

コードのポイント

• newNode関数： 新しいノードを作成し、初期化します。
• insertNode関数： 二分探索木の性質に従って、値を適切な位置に挿入します。
• printEvenNode関数： 中順走査を行いながら、各ノードの値を % 2 == 0 で判定し、偶数のみを出力します。

実行結果

プログラムを実行すると、次の出力が得られます。

All even nodes of the tree are :
12 30 54 80

まとめ

このように、二分探索木の偶数ノードを出力するには、木全体を一度巡回しながら各ノードの値を判定するだけで実現できます。計算量は全ノードを1回ずつ訪問するため O(n) となり、非常に効率的です。中順走査を利用すれば、偶数ノードが昇順に出力される点も覚えておくと便利です。