একটি বাইনারি গাছ দেওয়া. এখন আমাদেরকে 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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
