এটি একটি বাইনারি ট্রিতে সবচেয়ে বড় ইনডিপেন্ডেন্ট সেট (LIS) এর আকার বের করার C++ প্রোগ্রাম।
অ্যালগরিদম
শুরু. d ডেটা, l বাম চাইল্ড পয়েন্টার ও r ডান চাইল্ড পয়েন্টার ঘোষণা করতে n স্ট্রাকচার তৈরি করুন। দুটি ইন্টিজারের মধ্যে ম্যাক্সিমাম রিটার্ন করতে max() ফাংশন কল করুন। LIS() ফাংশন তৈরি করুন যা দেয়া বাইনারি ট্রিতে সবচেয়ে বড় ইনডিপেন্ডেন্ট সেটের আকার রিটার্ন করবে। বর্তমান নোড বাদ দিয়ে আকার বের করুন int size_excl = LIS(root->l) + LIS(root->r) বর্তমান নোড অন্তর্ভুক্ত করে আকার বের করুন int size_incl = 1; if (root->l) size_incl += LIS(root->l->l) + LIS(root->l->r) if (root->right) size_incl += LIS(root->r->l) + LIS(root->r->r) দুটি আকারের ম্যাক্সিমাম রিটার্ন করুন নতুন নোড তৈরি করার ফাংশন তৈরি করুন। শেষ।
উদাহরণ কোড
#include <iostream> using namespace std; struct n { int d; int lis; struct n *l, *r; }; int max(int x, int y) { return (x > y) ? x : y; } int LIS(struct n *root) { if (root == NULL) return 0; if (root->lis) return root->lis; if (root->l == NULL && root->r == NULL) return (root->lis = 1); int lis_excl = LIS(root->l) + LIS(root->r); int lis_incl = 1; if (root->l) lis_incl += LIS(root->l->l) + LIS(root->l->r); if (root->r) lis_incl += LIS(root->r->l) + LIS(root->r->r); root->lis = max(lis_incl, lis_excl); return root->lis; } struct n* newnode(int d) { struct n* t = (struct n *) malloc(sizeof(struct n)); t->d = d; t->l = t->r = NULL; t->lis = 0; return t; } int main() { struct n *root = newnode(30); root->l = newnode(20); root->l->l = newnode(10); root->l->r = newnode(7); root->l->r->l = newnode(9); root->l->r->r = newnode(6); root->r = newnode(50); root->r->r = newnode(26); cout << "সবচেয়ে বড় ইনডিপেন্ডেন্ট সেটের আকার " << LIS(root); return 0; }আউটপুট
সবচেয়ে বড় ইনডিপেন্ডেন্ট সেটের আকার 5
