最大独立集问题
当独立集是所有二叉树节点的子集，而该子集中的任何两个节点之间都没有边缘时。
现在，从一组元素中，我们将找到最长的独立集合。即，如果将元素用于形成二叉树，则所有最大子集，其中该子集中没有元素相互连接。
输入输出
Input: A binary tree.Output: Size of the Largest Independent Set is: 5
算法
longSetSize(root)
在这种算法中，将形成二叉树，该树的每个节点将保存数据和setSize。
输入- 二叉树的根节点。
输出-最长集合的大小。
Begin
if root = φ, then
return 0
if setSize(root) ≠ 0, then
setSize(root)
if root has no child, then
setSize(root) := 1
return setSize(root)
setSizeEx := longSetSize(left(root)) + longSetSize(right(root)) //excluding root
setSizeIn := 1
if left child exists, then
setSizeIn := setSizeIn + longSetSize(left(left(root))) + longSetSize(left(right(root)))
if right child exists, then
setSizeIn := setSizeIn + longSetSize(right(left(root))) + longSetSize(right(right(root)))
if setSizeIn > setSizeEx, then
setSize(root) := setSizeIn
else
setSize(root) := setSizeEx
return setSize(root)
End示例
#include <iostream>
using namespace std;
struct node {
int data;
int setSize;
node *left, *right;
};
int longSetSize(node *root) {
if (root == NULL)
return 0;
if (root->setSize != 0)
return root->setSize;
if (root->left == NULL && root->right == NULL) //when there is no child
return (root->setSize = 1);
//设置大小独占根是设置左边的大小和设置右边的大小
int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
int setSizeIn = 1; //inclusive root node
if (root->left) //if left sub tree is present
setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);
if (root->right) //if right sub tree is present
setSizeIn += longSetSize(root->right->left) +longSetSize(root->right->right);
root->setSize = (setSizeIn>setSizeEx)?setSizeIn:setSizeEx;
return root->setSize;
}
struct node* getNode(int data) { //create a new node with given data
node* newNode = new node;
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->setSize = 0;
return newNode;
}
int main() {
node *root = getNode(20);
root->left = getNode(8);
root->left->left = getNode(4);
root->left->right = getNode(12);
root->left->right->left = getNode(10);
root->left->right->right = getNode(14);
root->right = getNode(22);
root->right->right = getNode(25);
cout << "Size of the Largest Independent Set is: " << longSetSize(root);
}输出结果
Size of the Largest Independent Set is − 5