हमें एक पूर्णांक मान और एक चर 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 है या नहीं।
-
फ़ंक्शन के अंदर, जांचें कि रूट न्यूल है या नहीं, फिर झूठी वापसी करें
-
जांचें कि क्या रूट पीटीआर के बराबर नहीं है और रूट का डेटा + पीटीआर का डेटा एक्स के बराबर है, तो सही लौटें।
-
रूट, पीटीआर और मान x के बाएं पॉइंटर और एक्स, पीटीआर और एक्स के दाएं पॉइंटर को पास करके चेक फ़ंक्शन को दोबारा कॉल करें। अब जांचें कि क्या कोई शर्त सच हो रही है और फिर सही लौटें।
-
अन्यथा, झूठी वापसी करें।
-
x के रूप में योग के साथ जोड़े की गिनती की गणना करने के लिए एक फ़ंक्शन total_pairs बनाएं
-
फ़ंक्शन के अंदर, जांचें कि क्या ptr NULL है और फिर 0.
-
एक तर्क के रूप में रूट, पीआरटी और एक्स पास करके फ़ंक्शन चेक को कॉल करें। यदि फ़ंक्शन सही है तो कुल युग्मों के मान को 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