एक बाइनरी ट्री दिया गया है। अब हमें समान संख्या में 1 और 0 वाला सबसे बड़ा सबट्री खोजने का कार्य दिया गया है; ट्री में केवल 0 और 1 हैं।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम 0 मान वाले सभी नोड्स को -1 से बदलने जा रहे हैं। ऐसा करने से हमारा प्रोग्राम सरल हो जाएगा क्योंकि अब हमें योग 0 के बराबर वाले सबसे बड़े सबट्री को खोजने की आवश्यकता है।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <iostream> using namespace std; int maxi = -1; struct node { // हमारे ट्री नोड की संरचना int data; struct node *right, *left; }; struct node* newnode(int key){// नया नोड बनाने के लिए struct node* temp = new node; temp->data = key; temp->right = NULL; temp->left = NULL; return temp; } void inorder(struct node* root){ // ट्री को पार करना (उपयोग नहीं किया गया) if (root == NULL) return; inorder(root->left); cout << root->data << endl; inorder(root->right); } // फंक्शन जो 0 और 1 की समान संख्या वाले // सबट्री का अधिकतम आकार लौटाता है int calculatingmax(struct node* root){ int a = 0, b = 0; if (root == NULL) return 0; a = calculatingmax(root->right); // दायां सबट्री a = a + 1; // पैरेंट शामिल करना b = calculatingmax(root->left); // बायां सबट्री a = b + a; // वर्तमान सबट्री में नोड्स की संख्या if (root->data == 0) // यदि पूरे सबट्री का योग 0 है // यदि कुल आकार // वर्तमान मैक्स से अधिक है if (a >= maxi) maxi = a; return a; } int calc_sum(struct node* root){ // प्रत्येक नोड पर मान अपडेट करना if (root != NULL){ if (root->data == 0){ root->data = -1; } } int a = 0, b = 0; // यदि बायां चाइल्ड मौजूद है if (root->left != NULL) a = calc_sum(root->left); // यदि दायां चाइल्ड मौजूद है if (root->right != NULL) b = calc_sum(root->right); root->data += (a + b); return root->data; } // ड्राइवर कोड int main(){ struct node* root = newnode(1); root->right = newnode(0); root->right->right = newnode(1); root->right->right->right = newnode(1); root->left = newnode(0); root->left->left = newnode(1); root->left->left->left = newnode(1); root->left->right = newnode(0); root->left->right->left = newnode(1); root->left->right->left->left = newnode(1); root->left->right->right = newnode(0); root->left->right->right->left = newnode(0); root->left->right->right->left->left = newnode(1); calc_sum(root); calculatingmax(root); // cout << "h"; cout << maxi; return 0; }आउटपुट
6
उपरोक्त कोड की व्याख्या
उपरोक्त दृष्टिकोण में, हम 0 मान वाले सभी नोड्स को -1 से अपडेट करते हैं फिर अब हमने अपनी समस्या को योग 0 के बराबर वाले सबसे बड़े सबट्री को खोजने तक सीमित कर दिया है अब इस अपडेट के दौरान, हम प्रत्येक नोड को उस नोड पर रूटेड सबट्री के मान के साथ भी अपडेट करते हैं और अब हम दूसरे फंक्शन का उपयोग करके प्रत्येक नोड की गणना और जांच करते हैं जिसका मान 0 है और फिर उस ट्री में मौजूद नोड्स की अधिकतम संख्या निकालते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम समान संख्या में 1 और 0 वाला सबसे बड़ा सबट्री खोजने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।
