C++で二分探索木（BST）の指定範囲内のキーを出力する方法

この問題では、二分探索木（BST）と2つの値 k1・k2 が与えられ、木の中に存在する k1 から k2 の範囲内にあるすべての値を出力することが求められます。つまり、k1 以上かつ k2 以下の値をすべて、昇順（値が大きくなる順）で出力します。

二分探索木（BST）とは

二分探索木とは、次の3つの性質を満たす木構造のことです。

• 左部分木に含まれるノードは、すべて親ノードの値より小さい値を持つ
• 右部分木に含まれるノードは、すべて親ノードの値より大きい値を持つ
• 各部分木もまた二分探索木である必要がある。また、重複するノードは存在しない

具体例

理解を深めるために、具体的な例を見てみましょう。

入力：k1 = 12、k2 = 25
出力：15, 20, 24

解説： 木を走査すると、すべての要素が訪問されます。その中で、12以上25以下という範囲に該当するノード x（12 ≤ x ≤ 25）の値だけが出力されます。

ここでは、BSTの性質——「左部分木の要素は根より小さく、右部分木の要素は根より大きい」——を利用して解決します。さらに、BSTの行きがけ順ではなく中間順走査（in-order traversal）を使うことで、結果を自然に昇順で得ることができます。それでは、この問題を解くためのアルゴリズムを作成しましょう。

アルゴリズム

ステップ1：根ノードを k1 および k2 と比較する。
ステップ2：根の値が k1 より大きい場合、左部分木に対して再帰的に探索を呼び出す。
ステップ3：根の値が k2 より小さい場合、右部分木に対して再帰的に探索を呼び出す。
ステップ4：根ノードの値が範囲内にある場合、その値を出力する。

C++による実装例

それでは、このアルゴリズムに基づいて、問題を解くプログラムを作成してみましょう。

#include<bits/stdc++.h>
using namespace std;
class node{
    public:
        int data;
        node *left;
        node *right;
};
void nodesInRange(node *root, int k1, int k2){
    if ( NULL == root )
        return;
    if ( k1 < root->data )
        nodesInRange(root->left, k1, k2);
    if ( k1 <= root->data && k2 >= root->data )
        cout<<root->data<<"\t";
    if ( k2 > root->data )
        nodesInRange(root->right, k1, k2);
}
node* insert(int data){
    node *temp = new node();
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int main(){
    node *root = new node();
    int k1 = 12, k2 = 25;
    root = insert(20);
    root->left = insert(10);
    root->right = insert(24);
    root->left->left = insert(8);
    root->left->right = insert(15);
    root->right->right = insert(32);
    cout<<"指定範囲内のノードの値は\t";
    nodesInRange(root, k1, k2);
    return 0;
}

実行結果

指定範囲内のノードの値は 15 20 24.

このように、BSTの構造的な性質と中間順走査を組み合わせることで、範囲外の部分木への無駄な探索を省略でき、効率的に目的のキーだけを昇順で出力できます。