একটি বাইনারি ট্রিতে সবচেয়ে বড় স্বাধীন সেটের (LIS) আকার খোঁজার জন্য C++ প্রোগ্রাম

এটি একটি বাইনারি ট্রিতে সবচেয়ে বড় স্বাধীন সেটের (LIS) আকার খোঁজার জন্য একটি C++ প্রোগ্রাম।

অ্যালগরিদম

উদাহরণ কোড

#include  namespace ব্যবহার করে std;struct n { int d; int lis; struct n *l, *r;};int max(int ​​x, int y) { রিটার্ন (x> y) ? x :y;}int LIS(struct n *root) { if (root ==NULL) রিটার্ন 0; যদি (root->lis) রুট->লিস ফেরত দেয়; যদি (root->l ==NULL &&root->r ==NULL) রিটার্ন (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); রিটার্ন 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; রিটার্ন 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<<"সবচেয়ে বড় স্বাধীন সেটের আকার হল "< 
আউটপুট
 
সবচেয়ে বড় স্বাধীন সেটের মাপ হল ৫