C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で指定された範囲のBSTキーを出力します

この問題では、二分探索木の2つのノードが与えられます。そして、ツリーで発生するk1からk2の範囲のすべての値を出力する必要があります。つまり、k1より大きくk2より小さいすべての値を出力する必要があります。そして、これらすべてのキーを値の昇順で印刷する必要があります。

二分探索木 これらの3つのプロパティに従うツリーです-

  • 左側のサブツリーには、ノードの値よりも小さい値のノードがあります。

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

  • 取得されるサブツリーも二分探索木である必要があります。ツリーに重複ノードを含めることはできません。

例 、

C++で指定された範囲のBSTキーを出力します

トピックをよりよく理解するために例を見てみましょう

Input : k1 = 12 and k2 = 25.
Output : 15, 20, 24

ツリー - C++で指定された範囲のBSTキーを出力します

説明 −ツリーをトラバースすると、すべての要素がトラバースされ、12〜25の範囲にある要素が出力されます。つまり、ノードxの場合、12≤x≥25が出力されます。

ここでは、BSTのプロパティを使用してソリューションを見つけます。つまり、左側のサブツリーのすべての要素はルートよりも小さく、右側のサブツリーのすべての要素はルートノードよりも大きくなっています。そして、この問題を解決するためにBSTをトラバースするために使用します。それでは、この問題を解決するためのアルゴリズムを作成しましょう。

アルゴリズム

Step 1 : Compare the root node with the k1 and k2.
Step 2 : If root is greater than k1. Call left subtree for the search recursively.
Step 3 : If root is smaller than k2. Call right subtree for the search recursively.
Step 4 : If the root of the tree is in the range. Then print the root’s value.
例

では、このアルゴリズムに基づいて、問題を解決するためのプログラムを作成しましょう。

#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<<”The values of node within the range are\t”;
   nodesInRange(root, k1, k2);
   return 0;
}
出力 
The values of node within the range are 15 20 24.

  1. C++でBSTのノードを削除する

    二分探索木があるとします。 1つのキーkを取得し、指定されたキーkをBSTから削除して、更新されたBSTを返す必要があります。したがって、ツリーが次のような場合- そして、キーk =3の場合、出力ツリーは-になります。 これを解決するには、次の手順に従います- ルートノードを削除するためにdeleteRoot（）というメソッドを定義します。これは次のように機能します ルートがnullの場合、nullを返します ルートに右のサブツリーがない場合は、ルートの左に戻ります x：=ルートの後継者 xの左側を左に設定：=ルートの左側 ルート

  2. C++で特定のノードから距離kにあるすべてのノードを出力します

    この問題では、二分木、ターゲットノード、整数Kが与えられます。ターゲットノードから距離Kにあるツリーのすべてのノードを印刷する必要があります。 。 二分木 は、各ノードに最大2つのノード（1つまたは2つ/なし）を持つ特別なツリーです。 問題を理解するために例を見てみましょう K =2 ターゲットノード：9 出力 − 5 1 3. 説明 − 距離は、ノードの上位、下位、または同じレベルで取得できます。したがって、それに応じてノードを返します。 この問題を解決するには、ターゲットノードからK距離離れたノードのタイプを理解する必要があります。 上記の試験から、k個の離