C++で指定された範囲内にあるBST（二分探索木）の部分木を数える方法

はじめに

入力として二分探索木（BST）が与えられます。この記事の目的は、ノードの値がすべて指定された範囲（start〜end）に収まっているBST内の部分木の個数を求めることです。たとえば、startが5、endが50である場合、「すべてのノードの値が5以上50以下」という条件を満たす部分木の数を数えます。

入出力例

入力 − 下図の木、範囲 [3-6]

出力 − 範囲内にある木の数：2

説明 − 該当するのはノード4と6のみです。これらの部分木（NULL）は3〜6の範囲内にあります。

入力 − 下図の木、範囲 [12-20]

出力 − 範囲内にある木の数：3

説明 − 該当するのはノード16、14、20です。これらの部分木は12〜20の範囲内にあります。

プログラムで使用するアプローチ

• 構造体Btreenodeは、木のノードを作成するために使用します。infoメンバには整数値を格納し、left・rightポインタは自分自身を参照して左右の部分木を指します。
• 関数Btreenode* insert(int data)は、dataをinfoとし、left・rightポインタをNULLに設定した新しいノードを作成します。
• insert関数を呼び出してBSTを構築します。ルートの右側にノードを追加する場合は root->right = insert(70); のように、左側に追加する場合は root->left = insert(30); のように記述します。
• 変数lとhは、それぞれ範囲の最小値と最大値を格納します。
• 変数countは、l〜hの範囲内にある部分木の個数を格納します。初期値は0です。
• 関数getBtreeCount(Btreenode* root, int low, int high, int* count)は、BSTのルート、範囲の下限・上限、countのアドレスを引数として受け取り、再帰呼び出しごとにcountの値を更新します。
• 現在のrootがNULLかどうかを確認します。NULLであれば1を返します（NULLは木の一部ではないため）。
• 現在のノードについて、その左右の部分木に属するすべてのノードが指定範囲内にあるかどうかを、再帰呼び出し getBtreeCount(root->left, low, high, count); および getBtreeCount(root->right, low, high, count); によって確認します。
• 両方の部分木が範囲内にあり、かつ現在のノード自体も範囲内にある場合、現在のノードを根とする木は範囲内にあると判定できます。つまり if (left && right && root->info >= low && root->info <= high) が成立したときに ++*count; を実行し、1を返します。
• 最終的に、countには範囲内のすべての部分木の合計数が格納されます。
• 結果としてcountを出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// BSTのノード
struct Btreenode {
    int info;
    Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
    // ベースケース
    if (root == NULL)
       return 1;
       int left = getBtreeCount(root->left, low, high, count);
       int right = getBtreeCount(root->right, low, high, count);
       if (left && right && root->info >= low && root->info <= high) {
           ++*count;
       return 1;
    }
    return 0;
}
Btreenode* insert(int data){
    Btreenode* temp = new Btreenode;
    temp->info = data;
    temp->left = temp->right = NULL;
    return (temp);
}
int main(){
    /* 入力用のBST
         50
        / \
       30 70
      / \ / \
    20 40 60 80 */
    Btreenode* root = insert(50);
    root->left = insert(30);
    root->right = insert(70);
    root->left->left = insert(20);
    root->left->right= insert(40);
    root->right->left = insert(60);
    root->right->right = insert(80);
    int l = 10;
    int h = 50;
    int count=0;
    getBtreeCount(root, l, h, &count);
    cout << "Count of subtrees lying in range: " <<count;
    return 0;
}

出力

Count of subtrees lying in range: 3