C++の特定の範囲にあるBSTノードをカウントします

ノードと範囲で構成される二分探索木が与えられます。タスクは、指定された範囲内にあるノードの数を計算し、結果を表示することです。

二分探索木（BST）は、すべてのノードが以下のプロパティに従うツリーです-

• ノードの左側のサブツリーには、その親ノードのキー以下のキーがあります。

• ノードの右側のサブツリーには、その親ノードのキーよりも大きいキーがあります。

したがって、BSTはすべてのサブツリーを2つのセグメントに分割します。左側のサブツリーと右側のサブツリーで、次のように定義できます-

left_subtree（キー）≤node（キー）≤right_subtree（キー）

例

入力 −

範囲：[11、40]

出力 −カウントは次のとおりです：5

説明 −範囲[11、40]の間のノード値は14、19、27、31、および35であるため、特定の二分探索木には合計5つのノードがあります。

以下のプログラムで使用されているアプローチは次のとおりです

• データ、左ポインター、右ポインターを含むノードの構造を作成し、範囲を作成します

• ユーザーが入力する新しいノードを挿入する関数を作成します。

• 特定の範囲内にあるノードをカウントする別の関数を作成します。

• ルートがNULLかどうかを確認してから、

  を返します。

• ここで、if root-> data =Start AND root-> data =Endをチェックしてから、1を返します。

• ここで、IF root-> data <=high &&root-> data> =lowをチェックしてから、1 + getCount（root-> left、End、Start）+ recursively_call_count_function（root-> right、End、Start）

  を返します。

• それ以外の場合、root-> data right、End、Start）

• それ以外の場合は、recursively_call_count_function（root-> left、End、Start）を返します

例

#include<iostream>
using namespace std;
// A BST node
struct node{
   int data;
   struct node* left, *right;
};
// Utility function to create new node
node *newNode(int data){
   node *temp = new node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return (temp);
}
int findcount(node *root, int low, int high){
   // Base case
   if (!root){
      return 0;
   }
   if (root->data == high && root->data == low){
      return 1;
   }
   // If current node is in range, then include it in count and
   // recur for left and right children of it
   if (root->data <= high && root->data >= low){
      return 1 + findcount(root->left, low, high) +
      findcount(root->right, low, high);
   }
   else if (root->data < low){
      return findcount(root->right, low, high);
   }
   // Else recur for left child
   else{
      return findcount(root->left, low, high);
   }
}
// main function
int main(){
   // Let us construct the BST shown in the above figure
   node *root = newNode(27);
   root->left = newNode(14);
   root->right = newNode(35);
   root->left->left = newNode(10);
   root->left->right = newNode(19);
   root->right->left = newNode(31);
   root->right->right = newNode(42);
   int low = 10;
   int high = 50;
   cout << "Count of nodes between [" << low << ", " << high
   << "] is " << findcount(root, low, high);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

Count of nodes between [10, 50] is 7