当独立集是所有二叉树节点的子集,而该子集中的任何两个节点之间都没有边缘时。
现在,从一组元素中,我们将找到最长的独立集合。即,如果将元素用于形成二叉树,则所有最大子集,其中该子集中没有元素相互连接。
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