एक बाइनरी ट्री दिया। अब हमें 1 और 0 की समान संख्या वाले सबसे बड़े उपप्रकार को खोजने का काम सौंपा गया है; पेड़ में केवल 0 और 1 होते हैं।
समाधान खोजने के लिए दृष्टिकोण
इस दृष्टिकोण में, हम सभी नोड्स को 0 से -1 के मान से बदलने जा रहे हैं। ऐसा करने से हमारा प्रोग्राम आसान हो जाएगा क्योंकि अब हमें 0 के बराबर योग के साथ सबसे बड़ा सबट्री खोजने की जरूरत है।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <iostream>
using namespace std;
int maxi = -1;
struct node { // structure of our tree node
int data;
struct node *right, *left;
};
struct node* newnode(int key){// To create a new node
struct node* temp = new node;
temp->data = key;
temp->right = NULL;
temp->left = NULL;
return temp;
}
void inorder(struct node* root){ // traversing the tree(not used)
if (root == NULL)
return;
inorder(root->left);
cout << root->data << endl;
inorder(root->right);
}
// Function to return the maximum size of
// the sub-tree having an equal number of 0's and 1's
int calculatingmax(struct node* root){
int a = 0, b = 0;
if (root == NULL)
return 0;
a = calculatingmax(root->right); // right subtree
a = a + 1; // including parent
b = calculatingmax(root->left); // left subtree
a = b + a; // number of nodes at current subtree
if (root->data == 0) // if the sum of whole subtree is 0
// If the total size exceeds
// the current max
if (a >= maxi)
maxi = a;
return a;
}
int calc_sum(struct node* root){ // updating the values at each node
if (root != NULL){
if (root->data == 0){
root->data = -1;
}
}
int a = 0, b = 0;
// If left child exists
if (root->left != NULL)
a = calc_sum(root->left);
// If right child exists
if (root->right != NULL)
b = calc_sum(root->right);
root->data += (a + b);
return root->data;
}
// Driver code
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++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।