독립 집합은 해당 하위 집합의 두 노드 사이에 가장자리가 없을 때 모든 이진 트리 노드의 하위 집합입니다.
이제 요소 집합에서 가장 긴 독립 집합을 찾습니다. 즉, 요소가 이진 트리를 형성하는 데 사용되는 경우 해당 하위 집합의 요소가 서로 연결되지 않는 모든 가장 큰 하위 집합입니다.
입력 및 출력
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); // set size exclusive root is set size of left and set size of right 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