अवधारणा
किसी दिए गए बाइनरी ट्री के संबंध में, कार्य दिए गए बाइनरी ट्री में अधिकतम पूर्ण उप-वृक्ष का आकार निर्धारित करना है।
पूर्ण बाइनरी ट्री - एक बाइनरी ट्री को पूर्ण बाइनरी ट्री के रूप में माना जाता है यदि सभी स्तर पूरी तरह से अंतिम स्तर के बिना पूरी तरह से भरे हुए हैं और अंतिम स्तर में यथासंभव सभी कुंजियाँ हैं। यह नोट किया गया है कि सभी परफेक्ट बाइनरी ट्री पूर्ण बाइनरी ट्री हैं लेकिन नॉट ट्रू में उल्टा। यह देखा गया है कि यदि कोई वृक्ष पूर्ण नहीं है तो वह भी पूर्ण बाइनरी ट्री नहीं है।
इनपुट
2 / \ 3 4 / \ / \ 5 6 7 8 / \ / 9 10 11
आउटपुट
Size : 10 Inorder Traversal : 9 5 10 3 11 6 2 7 4 8 The above given tree is a complete binary tree.
इनपुट
51 / \ 31 61 / \ / \ 6 21 46 71 / 11
आउटपुट
Size : 4(With respect of right subtree) Inorder Traversal : 11 46 61 71 The above given tree is not a complete binary tree.
विधि
बस पेड़ को नीचे से ऊपर की ओर देखें। बच्चे से माता-पिता के लिए पुनरावर्तन में आने के संबंध में, हम उप-वृक्षों के बारे में जानकारी माता-पिता को स्थानांतरित कर सकते हैं। हस्तांतरित जानकारी केवल स्थिर समय में पूर्ण वृक्ष परीक्षण (पैरेंट नोड के लिए) करने के लिए माता-पिता द्वारा लागू की जा सकती है। इस मामले में, बाएँ और दाएँ दोनों उप-पेड़ों को माता-पिता की जानकारी बताने की आवश्यकता होती है कि वे सही हैं या नहीं और पूर्ण हैं या नहीं और उन्हें अब तक मिले पूर्ण बाइनरी ट्री का अधिकतम आकार वापस करने की भी आवश्यकता है।
हमें ध्यान देना चाहिए कि उप-वृक्षों को सबसे बड़ा पूर्ण उप-वृक्ष निर्धारित करने के लिए निम्न जानकारी को पेड़ पर स्थानांतरित करने की आवश्यकता है ताकि हम पूर्ण बाइनरी ट्री संपत्ति को सत्यापित करने के लिए माता-पिता के डेटा के साथ अधिकतम आकार की तुलना कर सकें।
-
यह सत्यापित करने के लिए एक बूल चर मौजूद होना चाहिए कि बायां बच्चा या दायां बच्चा उप-वृक्ष बिल्कुल सही और पूर्ण है या नहीं।
-
फिर से हमें यह सत्यापित करना होगा कि रिकर्सन में बाएं और दाएं बच्चे कॉल से हमें पता चलता है कि माता-पिता उप-पेड़ पूर्ण है या नहीं, 3 मामलों का पालन करके -
-
यह देखा गया है कि यदि बायां उपप्रकार पूर्ण है और दायां पूर्ण है और ऊंचाई भी समान है तो उप-वृक्ष जड़ को पूर्ण बाइनरी उपट्री के रूप में भी माना जाता है जिसका आकार बाएं और दाएं उपट्री के योग के बराबर होता है (वर्तमान रूट के लिए)।
-
यह देखा गया है कि यदि लेफ्ट सबट्री पूर्ण है और राइट परफेक्ट है और लेफ्ट की ऊंचाई राइट से एक से बड़ी है तो सब-ट्री रूट पूर्ण बाइनरी सबट्री है जिसका साइज लेफ्ट और राइट सबट्री प्लस वन (वर्तमान रूट के लिए) के योग के बराबर है। . लेकिन रूट सबट्री को परफेक्ट बाइनरी सबट्री घोषित नहीं किया जा सकता क्योंकि इस मामले में इसका लेफ्ट चाइल्ड परफेक्ट नहीं है।
-
अन्यथा इस उप-वृक्ष को पूर्ण द्विआधारी वृक्ष के रूप में नहीं माना जा सकता है और बाएं या दाएं उप-वृक्षों में अब तक पाए गए सबसे बड़े आकार के पूर्ण उप-वृक्ष को वापस नहीं किया जा सकता है। इसलिए यह निष्कर्ष निकाला जा सकता है कि यदि वृक्ष पूर्ण नहीं है तो यह नहीं है परिपूर्ण भी।
-
उदाहरण
//This is a C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node structure of the tree
struct node1 {
int data;
struct node1* left;
struct node1* right;
};
// For creating a new node
struct node1* newNode(int data){
struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
node1->data = data;
node1->left = NULL;
node1->right = NULL;
return node1;
};
// Shows structure for return type of
// function findPerfectBinaryTree
struct returnType {
// For storing if sub-tree is perfect or not
bool isPerfect;
// For storing if sub-tree is complete or not
bool isComplete;
// Indicates size of the tree
int size1;
// Root of biggest complete sub-tree
node1* rootTree;
};
// Shows helper function that returns height
// of the tree given size
int getHeight(int size1){
return ceil(log2(size1 + 1));
}
// Shows function to return the biggest
// complete binary sub-tree
returnType findCompleteBinaryTree(struct node1* root){
// Declaring returnType that
// needs to be returned
returnType rt1;
// If root is NULL then it is considered as both
// perfect and complete binary tree of size 0
if (root == NULL) {
rt1.isPerfect = true;
rt1.isComplete = true;
rt1.size1 = 0;
rt1.rootTree = NULL;
return rt1;
}
// Shows recursive call for left and right child
returnType lv1 = findCompleteBinaryTree(root->left);
returnType rv1 = findCompleteBinaryTree(root->right);
// CASE - A
// It has been seen that if left sub-tree is perfect and right is
// complete and there height is also same then sub-tree root
// is also complete binary sub-tree with size equal to
// sum of left and right subtrees plus one for current root
if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
rt1.isComplete = true;
// It has been seen that if right sub-tree is perfect then
// root is also perfect
rt1.isPerfect = (rv1.isPerfect ? true : false);
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
// CASE - B
// It has been seen if left sub-tree is complete and right is
// also perfect and the left height is greater than height of right by one
// then sub-tree root will be a complete binary sub-tree with the size equal to
// sum of left and right subtrees plus one for current root.
// But sub-tree cannot be perfect binary sub-tree.
if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
rt1.isComplete = true;
rt1.isPerfect = false;
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
// CASE - C
// Otherwise this sub-tree cannot be a complete binary tree
// and simply return the biggest sized complete sub-tree
// found till now in the left or right sub-trees
rt1.isPerfect = false;
rt1.isComplete = false;
rt1.size1 = max(lv1.size1, rv1.size1);
rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree :
rv1.rootTree);
return rt1;
}
// Shows function to print the inorder traversal of the tree
void inorderPrint(node1* root){
if (root != NULL) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
// Driver code
int main(){
// Creating the tree
struct node1* root = newNode(50);
root->left = newNode(30);
root->right = newNode(60);
root->left->left = newNode(5);
root->left->right = newNode(20);
root->right->left = newNode(45);
root->right->right = newNode(70);
root->right->left->left = newNode(10);
// Getting the biggest sized complete binary sub-tree
struct returnType ans1 = findCompleteBinaryTree(root);
cout << "Size : " << ans1.size1 << endl;
// Printing the inorder traversal of the found sub-tree
cout << "Inorder Traversal : ";
inorderPrint(ans1.rootTree);
return 0;
} आउटपुट
Size : 4 Inorder Traversal : 10 45 60 70