हमें इनपुट के रूप में दो बाइनरी सर्च ट्री और एक वेरिएबल x दिया गया है। लक्ष्य प्रत्येक पेड़ से नोड्स के जोड़े को ढूंढना है ताकि नोड्स के मूल्य का योग x के बराबर हो। BST_1 से नोड 1 और BST_2 से नोड 2 लें और दोनों का डेटा भाग जोड़ें। यदि योग =x. वेतन वृद्धि की संख्या।
आइए उदाहरणों से समझते हैं।
इनपुट
आउटपुट − दो BST से युग्मों की संख्या जिनका योग किसी दिए गए मान x के बराबर है − 1
. हैस्पष्टीकरण - जोड़ी है (8,6)
इनपुट
आउटपुट −दो बीएसटी से युग्मों की संख्या जिनका योग किसी दिए गए मान x के बराबर है − 2
. हैस्पष्टीकरण - जोड़े हैं (5,15) और (4,16)
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम एक पुनरावृत्त इनऑर्डर विधि का उपयोग करके बीएसटी को पार करेंगे। सबसे छोटे नोड से सबसे बड़े बीएसटी 1 को पुनरावृत्त इनऑर्डर विधि का उपयोग करके और बीएसटी 2 को पुनरावृत्त इनऑर्डर विधि के विपरीत से पार करें। दोनों BST के वर्तमान नोड्स का योग लें। यदि योग x वृद्धि गणना है। यदि sum>x तो BST 2 में वर्तमान नोड के इनऑर्डर पूर्ववर्ती पर जाएँ। यदि sum
दो पेड़ BST_1 और BST_2 लें जिनमें पूर्णांक डेटा भाग हो और बाएँ, दाएँ पॉइंटर्स चाइल्ड नोड्स की ओर हों।
फ़ंक्शन इन्सर्ट_नोड (इंट डेटा) डेटा के साथ ट्री में एक नया नोड सम्मिलित करता है और इसके लिए एक पॉइंटर लौटाता है।
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 के रूप में लें।
पुनरावृत्त इनऑर्डर ट्रैवर्सल के लिए दो चर ट्री* स्टैक_टॉप_1, *स्टैक_टॉप_2;
दो स्टैक स्टैक बनाएं स्टैक_1, स्टैक_2;
अब लूप के दौरान बाहरी शुरू करें।
जबकि लूप का उपयोग करके BST_1 के सबसे बाएं (सबसे छोटे) नोड पर जाएं और सभी नोड्स को स्टैक_1 पर पुश करें_1
लूप के दौरान BST_2 के सबसे दाहिने (सबसे बड़े) नोड पर जाएं और सभी नोड्स को स्टैक_2 पर पुश करें
यदि कोई स्टैक खाली है तो लूप के दौरान बाहरी को तोड़ दें।
दोनों स्टैक के शीर्ष नोड्स लें और उनके डेटा भागों को जोड़ें और अस्थायी रूप से स्टोर करें।
अगर अस्थायी (योग) ==x तो वेतन वृद्धि गिनती। पॉप ऑपरेशन का उपयोग करके स्टैक_1 और स्टैक_2 दोनों से शीर्ष तत्वों को निकालें।
BST_1=stack_1->दाएं और BST_2=stack_2->बाएं (BST_1 में अगला उत्तराधिकारी और BST_2 में पूर्ववर्ती)
यदि temp
IF temp>
x तो केवल स्टैक_2 से ऊपर निकालें और BST_1 में अगले पूर्ववर्ती पर जाएं।
बाहरी समय के अंत में, गिनती में कई जोड़े होते हैं जिनमें दोनों बीएसटी के नोड का योग 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