हमें एक पूर्णांक मान और एक वेरिएबल x दिया गया है और कार्य बाइनरी ट्री बनाना है और उन जोड़ों को ढूंढना है जिनका योग दिए गए मान x के बराबर है।
उदाहरण के लिए
इनपुट
int x = 5, मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:
आउटपुट
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
व्याख्या
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या बाइनरी ट्री में कोई जोड़ा मौजूद है जिसका योग दिए गए मान x के बराबर है जो 5 है। तो बने जोड़े हैं (2, 3) और (1, 4)।
इनपुट
int x = 8, मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:
आउटपुट
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
व्याख्या
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या बाइनरी ट्री में कोई जोड़ा मौजूद है जिसका योग दिए गए मान x के बराबर है जो 8 है। तो बने जोड़े हैं (2, 6), (4, 4) और (5, 3)।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
एक नोड का स्ट्रक्चर बनाएं जिसमें डेटा भाग और बाएं और दाएं पॉइंटर हों जो बाएं और दाएं सबट्री की ओर इशारा करेंगे।
एक पूर्णांक मान इनपुट करें और बाएं और दाएं पॉइंटर्स के माध्यम से नोड में डेटा दर्ज करके बाइनरी ट्री बनाएं।
x का मान इनपुट करें जिसका उपयोग योग मान x वाले जोड़ों की गणना के लिए किया जाएगा।
एक बूलियन फ़ंक्शन बनाएं जो जांचे कि जोड़ों का योग x है या नहीं।
फ़ंक्शन के अंदर, जांचें कि क्या रूट NULL है तो False लौटाएं।
जांचें कि क्या रूट ptr के बराबर नहीं है और रूट का डेटा + ptr का डेटा x के बराबर है तो True लौटाएं।
चेक फ़ंक्शन को रिकर्सिवली कॉल करें रूट के लेफ्ट पॉइंटर, ptr और मान x को पास करके और रूट के राइट पॉइंटर, ptr और x को भी पास करके। अब जांचें कि क्या कोई शर्त ट्रू लौटाती है तो ट्रू लौटाएं।
अन्यथा, फॉल्स लौटाएं।
x के योग वाले जोड़ों की गिनती की गणना करने के लिए total_pairs फ़ंक्शन बनाएं।
फ़ंक्शन के अंदर, जांचें कि क्या ptr NULL है तो 0 लौटाएं।
रूट, ptr और x को आर्गुमेंट के रूप में पास करके चेक फ़ंक्शन को कॉल करें। यदि फ़ंक्शन ट्रू लौटाता है तो कुल जोड़ों के मान को 1 से बढ़ाएं।
total_pairs फ़ंक्शन को रिकर्सिवली कॉल करें रूट, ptr के लेफ्ट पॉइंटर, x और total को पास करके और रूट, ptr के राइट पॉइंटर, x और total को भी पास करके।
परिणाम को total वेरिएबल में स्टोर पूर्णांक मान के रूप में प्रिंट करें।
उदाहरण
#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
