นับคู่จากสอง BST ที่มีผลรวมเท่ากับค่าที่กำหนด x ใน C ++

เราได้รับต้นไม้การค้นหาไบนารีสองต้นเป็นอินพุตและตัวแปร x เป้าหมายคือการหาคู่ของโหนดจากต้นไม้แต่ละต้นเพื่อให้ผลรวมของมูลค่าของโหนดเท่ากับ x รับโหนด 1 จาก BST_1 และโหนด 2 จาก BST_2 และเพิ่มส่วนข้อมูลของทั้งสอง ถ้า sum=x จำนวนที่เพิ่มขึ้น

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล

ผลผลิต − การนับคู่จากสอง BST ที่ผลรวมเท่ากับค่าที่กำหนด x คือ − 1

คำอธิบาย − คู่คือ (8,6)

ป้อนข้อมูล

ผลผลิต −จำนวนคู่จากสอง BST ที่ผลรวมเท่ากับค่าที่กำหนด x คือ − 2

คำอธิบาย – คู่คือ (5,15) และ (4,16)

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะสำรวจ BST โดยใช้วิธีการ inorder แบบวนซ้ำ สำรวจ BST 1 จากโหนดที่เล็กที่สุดไปยังโหนดที่ใหญ่ที่สุดโดยใช้วิธี inorder แบบวนซ้ำ และข้ามผ่าน BST 2 จากวิธีย้อนกลับของวิธี inorder แบบวนซ้ำ หาผลรวมของโหนดปัจจุบันของทั้งสอง BST ถ้าผลรวมเป็น x ให้นับเพิ่ม หาก sum>x ย้ายไปที่บรรพบุรุษที่ไม่เรียงลำดับของโหนดปัจจุบันใน BST 2 หาก sum

• นำต้นไม้สองต้น BST_1 และ BST_2 ที่มีส่วนข้อมูลจำนวนเต็มและชี้ไปทางซ้ายขวาไปยังโหนดย่อย

• ฟังก์ชัน insert_node(ข้อมูล int) แทรกโหนดใหม่ลงในทรีด้วยข้อมูลและส่งคืนตัวชี้ไปยังโหนดนั้น

• สร้าง BST ทั้งสองโดยใช้ inser_node() และส่งต่อไปยัง BST_sum_x(Tree* BST_1, Tree* BST_2, int x)

• ฟังก์ชัน BST_sum_x(Tree* BST_1, Tree* BST_2, int x) รับโหนดรูทของต้นไม้ทั้งสองและส่งคืนค่าจำนวนโหนดของคู่ที่มีผลรวมของส่วนข้อมูลเป็น x

• ให้นับเริ่มต้นเป็น 0 สำหรับจำนวนคู่ที่มีผลรวม x

• สำหรับการวนซ้ำ inorder แบบวนซ้ำ ให้ใช้สองตัวแปร Tree* stack_top_1, *stack_top_2;

• สร้างสองกอง stack stack_1, stack_2;

• ตอนนี้เริ่มภายนอกในขณะที่วนซ้ำ

• ไปที่โหนดซ้ายสุด (เล็กที่สุด) ของ BST_1 โดยใช้ while loop และผลักโหนดทั้งหมดไปที่ stack_1

• ไปที่โหนดขวาสุด (ที่ยิ่งใหญ่ที่สุด) ของ BST_2 โดยใช้ while วนแล้วดันโหนดทั้งหมดไปที่ stack_2

• หากสแต็คใดว่างให้ทำลายส่วนนอกในขณะที่วง

• นำโหนดบนสุดของทั้งสองสแต็กและเพิ่มส่วนข้อมูลและเก็บไว้ในชั่วคราว

• ถ้า temp ( sum) ==x ให้นับการเพิ่ม ลบองค์ประกอบด้านบนออกจากทั้ง stack_1 และ stack_2 โดยใช้ป๊อปอัป

• ตั้งค่า BST_1=stack_1->right และ BST_2=stack_2->left (ตัวต่อถัดไปใน BST_1 และรุ่นก่อนใน BST_2 )

• หาก temp

• IF temp> x ให้ลบเฉพาะด้านบนจาก stack_2 และย้ายไปยังรุ่นก่อนหน้าใน BST_1

• ในตอนท้ายของด้านนอกในขณะที่การนับมีจำนวนคู่ที่มีโหนดของ BST ทั้งสองที่มีผลรวม x

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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