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

合計がC++の指定された値xに等しい2つのBSTからペアをカウントします


入力として2つの二分探索木と変数xが与えられます。目標は、ノードの値の合計がxに等しくなるように、各ツリーからノードのペアを見つけることです。 BST_1からノード1を取得し、BST_2からノード2を取得して、両方のデータ部分を追加します。 sum=xの場合。インクリメントカウント。

例を挙げて理解しましょう。

入力

合計がC++の指定された値xに等しい2つのBSTからペアをカウントします

出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 1

説明 −ペアは(8,6)

入力

合計がC++の指定された値xに等しい2つのBSTからペアをカウントします

出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 2

説明 −ペアは(5,15)と(4,16)

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

このアプローチでは、反復順序法を使用してBSTをトラバースします。反復順序法を使用して最小ノードから最大ノードにBST1をトラバースし、反復順序法の逆からBST2をトラバースします。両方のBSTの現在のノードの合計を取ります。合計がxインクリメントカウントの場合。 sum> xの場合、BST2の現在のノードの順序の前の先行に移動します。sum

  • 整数データ部分と子ノードへの左右のポインタを持つ2つのツリーBST_1とBST_2を取ります。

  • 関数insert_node(int data)は、データを含むツリーに新しいノードを挿入し、そのノードへのポインターを返します。

  • inser_node()を使用して両方のBSTを作成し、BST_sum_x(Tree * BST_1、Tree * BST_2、int x)に渡します。

  • 関数BST_sum_x(Tree * BST_1、Tree * BST_2、int x)は、両方のツリーのルートノードを取得し、データ部分の合計をxとして持つノードのペアの数を返します。

  • 合計xのペアの数の初期カウントを0とします。

  • 反復的な順序トラバーサルの場合、2つの変数Tree * stack_top_1、* stack_top_2;

    を取ります。
  • 2つのスタックを作成しますstackstack_1、stack_2;

  • 次に、外側のwhileループを開始します。

  • whileループを使用してBST_1の左端(最小)のノードに移動し、すべてのノードをstack_1にプッシュします

  • whileループを使用してBST_2の右端(最大)のノードに移動し、すべてのノードをstack_2にプッシュします

  • スタックのいずれかが空の場合は、外側のwhileループを解除します。

  • 両方のスタックの最上位ノードを取得し、それらのデータパーツを追加して、一時的に保存します。

  • temp(sum)==xの場合、カウントをインクリメントします。ポップ操作を使用して、stack_1とstack_2の両方から最上位の要素を削除します。

  • BST_1 =stack_1->rightおよびBST_2=stack_2-> left(BST_1の次の後続およびBST_2の先行)を設定します

  • temp

  • temp> xの場合、stack_2からtopのみを削除し、BST_1の次の先行タスクに移動します。

  • 外側のwhileの終わりに、countには、合計xを持つ両方のBSTのノードを持つペアの数があります。

  • 結果としてカウントを返します。

#include <bits/stdc++.h>
using namespace std;
struct Tree{
   int data;
   Tree* left, *right;
};
Tree* insert_node(int data){
   Tree* newNode = (Tree*)malloc(sizeof(Tree));
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
}
int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
   int count = 0;
   Tree* stack_top_1, *stack_top_2;
   stack<Tree*> stack_1, stack_2;
   if (BST_1 == NULL || BST_2 == NULL){
      return 0;
   }
   while (1){
      while (BST_1 != NULL){
         stack_1.push(BST_1);
         BST_1 = BST_1->left;
      }
      while (BST_2 != NULL){
         stack_2.push(BST_2);
         BST_2 = BST_2->right;
      }
      if (stack_1.empty() || stack_2.empty()){
         break;
      }
      stack_top_1 = stack_1.top();
      stack_top_2 = stack_2.top();
      int temp = stack_top_1->data + stack_top_2->data;
      if (temp == x){
         count++;
         stack_1.pop();
         stack_2.pop();
         BST_1 = stack_top_1->right;
         BST_2 = stack_top_2->left;
      }
      else if (temp < x){
         stack_1.pop();
         BST_1 = stack_top_1->right;
      }
      else{
         stack_2.pop();
         BST_2 = stack_top_2->left;
      }
   }
   return count;
}
int main(){
   //BST 1
   Tree* BST_1 = insert_node(15);
   BST_1->left = insert_node(10);
   BST_1->right = insert_node(8);
   BST_1->left->left = insert_node(12);
   BST_1->left->right = insert_node(24);
   BST_1->right->left = insert_node(16);
   //BST 2
   Tree* BST_2 = insert_node(20);
   BST_2->left = insert_node(16);
   BST_2->right = insert_node(4);
   BST_2->left->left = insert_node(18);
   BST_2->left->right = insert_node(28);
   BST_2->right->left = insert_node(22);
   int x = 28;
   cout<<"Count of pairs from two BSTs whose sum is equal to a given value x ar: "<<BST_sum_x(BST_1, BST_2, x);
   return 0;
}

出力

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

Count of pairs from two BSTs whose sum is equal to a given value x ar: 1

  1. 合計がC++の指定された値xに等しい、ソートされた二重リンクリストのトリプレットをカウントします

    整数値を含むソートされた二重リンクリストが与えられます。目標は、積が指定された値xに等しいトリプレットを見つけることです。入力リンクリストが3-4-1-2で、xが6の場合、カウントは1になります(トリプレット(3,1,2)) 例 入力 linked list: [ 3−4−13−5−10−10−0 ] x=20 出力 Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 2 説

  2. ソートされた二重リンクリスト内のトリプレットをカウントします。このリストの積は、C++で指定された値xに等しくなります。

    整数値を含むソートされた二重リンクリストが与えられます。目標は、積が与えられた値xに等しいトリプレットを見つけることです。入力リンクリストが3−4−1−2で、xが6の場合、カウントは1になります(トリプレット(3,1,2)) 例 入力 linked list: [ 200−4−16−5−10−10−2 ] x=200 出力 Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: