अवधारणा
दिए गए बाइनरी ट्री के संबंध में, कार्य दिए गए बाइनरी ट्री में अधिकतम पूर्ण उप-ट्री का आकार निर्धारित करना है।
पूर्ण बाइनरी ट्री - एक बाइनरी ट्री को पूर्ण बाइनरी ट्री माना जाता है यदि सभी स्तर संभवतः अंतिम स्तर को छोड़कर पूरी तरह भरे हुए हैं और अंतिम स्तर में सभी कुंजियां यथासंभव बाईं ओर हैं। ध्यान दें कि सभी परफेक्ट बाइनरी ट्री पूर्ण बाइनरी ट्री हैं लेकिन विपरीत सत्य नहीं है। यदि ट्री पूर्ण नहीं है तो यह परफेक्ट बाइनरी ट्री भी नहीं है।
उदाहरण
इनपुट
2
/ \
3 4
/ \ / \
5 6 7 8
/ \ /
9 10 11
आउटपुट
Size : 10 Inorder Traversal : 9 5 10 3 11 6 2 7 4 8 उपरोक्त दिया गया ट्री एक पूर्ण बाइनरी ट्री है।
इनपुट
51
/ \
31 61
/ \ / \
6 21 46 71
/
11
आउटपुट
Size : 4 (दाएं उपट्री के संबंध में) Inorder Traversal : 11 46 61 71 उपरोक्त दिया गया ट्री पूर्ण बाइनरी ट्री नहीं है।
विधि
बस ट्री को नीचे से ऊपर की ओर पार करें। फिर चाइल्ड से पैरेंट की ओर पुनरावर्तन में ऊपर आते समय, हम उप-ट्री के बारे में जानकारी पैरेंट को स्थानांतरित कर सकते हैं। स्थानांतरित जानकारी का उपयोग पैरेंट द्वारा पूर्ण ट्री परीक्षण (पैरेंट नोड के लिए) केवल स्थिर समय में करने के लिए किया जा सकता है। इस मामले में, बाएं और दाएं दोनों उप-ट्री को पैरेंट को बताना होगा कि वे परफेक्ट हैं या नहीं और पूर्ण हैं या नहीं और उन्हें अब तक मिले पूर्ण बाइनरी ट्री का अधिकतम आकार भी वापस करना होगा।
C++ कार्यान्वयन
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
struct node1 {
int data;
struct node1* left;
struct node1* right;
};
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;
}
struct returnType {
bool isPerfect;
bool isComplete;
int size1;
node1* rootTree;
};
int getHeight(int size1){
return ceil(log2(size1 + 1));
}
returnType findCompleteBinaryTree(struct node1* root){
returnType rt1;
if (root == NULL) {
rt1.isPerfect = true;
rt1.isComplete = true;
rt1.size1 = 0;
rt1.rootTree = NULL;
return rt1;
}
returnType lv1 = findCompleteBinaryTree(root->left);
returnType rv1 = findCompleteBinaryTree(root->right);
// CASE - A
if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
rt1.isComplete = true;
rt1.isPerfect = (rv1.isPerfect ? true : false);
rt1.size1 = lv1.size1 + rv1.size1 + 1;
rt1.rootTree = root;
return rt1;
}
// CASE - B
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
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;
}
void inorderPrint(node1* root){
if (root != NULL) {
inorderPrint(root->left);
cout << root->data << " ";
inorderPrint(root->right);
}
}
int main(){
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);
struct returnType ans1 = findCompleteBinaryTree(root);
cout << "Size : " << ans1.size1 << endl;
cout << "Inorder Traversal : ";
inorderPrint(ans1.rootTree);
return 0;
}
आउटपुट
Size : 4 Inorder Traversal : 10 45 60 70