นับคู่ในไบนารีทรีที่มีผลรวมเท่ากับค่าที่กำหนด x ใน C++

เราได้รับค่าจำนวนเต็มและตัวแปร x และภารกิจคือการสร้างไบนารีทรีและค้นหาคู่ที่มีผลรวมเท่ากับค่าที่กำหนด x

ตัวอย่าง

อินพุต

int x =5 ต้นไม้ที่จะสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

Count of pairs in a binary tree whose sum is equal to a given value x are: 2

คำอธิบาย

we are given with an array of integer values that is used to form a binary
tree and we will check whether there is a pair present in a binary tree whose sum
equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).

อินพุต

int x =8 ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

Count of pairs in a binary tree whose sum is equal to a given value x are: 3

คำอธิบาย

we are given with an array of integer values that is used to form a binary
tree and we will check whether there is a pair present in a binary tree whose sum
equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).

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

• สร้างโครงสร้างของโหนดที่มีส่วนข้อมูลและตัวชี้ซ้ายและขวาซึ่งจะชี้ไปที่ทรีย่อยด้านซ้ายและขวา

• ป้อนค่าจำนวนเต็มและใช้เพื่อสร้างไบนารีทรีโดยการป้อนข้อมูลไปยังโหนดผ่านพอยน์เตอร์ซ้ายและขวา

• ป้อนค่าของ x ซึ่งจะใช้ในการคำนวณคู่ที่มีค่าผลรวมเท่ากับ x

• สร้างฟังก์ชันบูลีนเพื่อตรวจสอบว่าผลรวมของคู่เป็น x หรือไม่

• ภายในฟังก์ชัน ตรวจสอบว่า root เป็น NULL แล้วคืนค่า False

• ตรวจสอบว่า root ไม่เท่ากับ ptr และข้อมูลของ root + data ของ ptr เท่ากับ x แล้วคืนค่า True

• ฟังก์ชันตรวจสอบการเรียกซ้ำโดยส่งตัวชี้ซ้ายของรูท ptr และค่า x และตัวชี้ขวาของ x, ptr และ x ด้วย ตอนนี้ตรวจสอบว่าเงื่อนไขใด ๆ ที่คืนค่าเป็นจริงแล้วคืนค่าจริงหรือไม่

• มิฉะนั้น คืนค่าเท็จ

• สร้างฟังก์ชัน total_pairs เพื่อคำนวณจำนวนคู่โดยมีผลรวมเป็น x

• ภายในฟังก์ชัน ให้ตรวจสอบว่า ptr เป็น NULL แล้วคืนค่า 0

• เรียกใช้การตรวจสอบฟังก์ชันโดยส่ง root, ptr และ x เป็นอาร์กิวเมนต์ หากฟังก์ชันคืนค่าเป็น จริง ให้เพิ่มมูลค่าของคู่ทั้งหมด 1

• เรียกใช้ฟังก์ชัน total_pairs แบบเรียกซ้ำโดยการส่งผ่านรูท ตัวชี้ด้านซ้ายของ ptr x และผลรวม และยังส่งผ่านรูท ตัวชี้ด้านขวาของ ptr x และผลรวมด้วย

• พิมพ์ผลลัพธ์เป็นค่าจำนวนเต็มที่เก็บในผลรวมของตัวแปร

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
struct tree_node {
   int data;
   tree_node *left, *right;
};
tree_node* create_node(int data){
   tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
   newNode−>data = data;
   newNode−>left = newNode−>right = NULL;
}
bool check(tree_node* root, tree_node* ptr, int x){
   if(root==NULL){
      return false;
   }
   if (root != ptr && ((root−>data + ptr−>data) == x)){
      return true;
   }
   if (check(root−>left, ptr, x) || check(root−>right, ptr, x)){
      return true;
   }
   return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
   if(ptr == NULL){
      return;
   }
   if(check(root, ptr, x) == true){
      total++;
   }
   total_pairs(root, ptr−>left, x, total);
   total_pairs(root, ptr−>right, x, total);
}
int main(){
   int x = 5;
   int total = 0;
   tree_node* root = create_node(5);
   root−>left = create_node(2);
   root−>right = create_node(3);
   root−>left−>left = create_node(1);
   root−>left−>right = create_node(4);
   root−>right−>left = create_node(6);
   total_pairs(root, root, x, total);
   total = total / 2;
   cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of pairs in a binary tree whose sum is equal to a given value x are: 2