C ++程序在给定的二叉树中查找最大独立集(LIS)的大小

2024-04-22 12:54:21 314

算法

Begin. Create a structure n to declare data d, a left child pointer l and a right child pointer r. Call a function max() to return maximum between two integers. Create a function LIS() to return the size of the largest independent set in a given binary tree. Calculate size excluding the current node int size_excl = LIS(root->l) + LIS(root->r) Calculate size including the current node 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) Return the maximum of two sizes Create a function to create newnode. End.

范例程式码

#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<<"Size of the Largest Independent Set is "<< LIS(root); return 0; }

输出结果

Size of the Largest Independent Set is 5

C ++程序在给定的二叉树中查找最大独立集(LIS)的大小

算法

范例程式码

热门推荐

随机推荐