数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 程序可在提供的二叉树中找到最大独立集 (LIS) 的大小
这是一款 C++ 程序，可查找给定二叉树中最大独立集 (LIS) 的大小。
算法
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
更新日期：2019 年 7 月 30 日
140 次浏览
广告