Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

किसी दिए गए बाइनरी ट्री में सबसे बड़ा BST सबट्री खोजें - C++ में 1 सेट करें

इस समस्या में हमें एक बाइनरी ट्री BT दिया जाता है। हमारा काम है किसी दिए गए बाइनरी ट्री में सबसे बड़ा BST सबट्री ढूंढना

बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।

बाइनरी सर्च ट्री (बीएसटी) एक ऐसा पेड़ है जिसमें सभी नोड्स नीचे बताए गए गुणों का पालन करते हैं -

  • बाएँ उप-वृक्ष की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम है।

  • दाएँ उपट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या उसके बराबर होता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट :

किसी दिए गए बाइनरी ट्री में सबसे बड़ा BST सबट्री खोजें - C++ में 1 सेट करें

आउटपुट :3

स्पष्टीकरण

Full binary tree is a BST.

समाधान दृष्टिकोण

समस्या का एक सरल समाधान पेड़ के क्रम में ट्रैवर्सल करना है। और पेड़ के प्रत्येक नोड के लिए, जांचें कि उसके उपप्रकार बीएसटी हैं या नहीं। अंत में सबसे बड़े सबट्री का आकार लौटाएं जो एक बीएसटी है।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include<bits/stdc++.h>
using namespace std;
class node{
   public:
   int data;
   node* left;
   node* right;
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int findTreeSize(node* node) {
   if (node == NULL)
      return 0;
   else
      return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
   if (node == NULL)
      return 1;
   if (node->left != NULL && node->left->data > node->data)
      return 0;
   if (node->right != NULL && node->right->data < node->data)
      return 0;
   if (!isBSTree(node->left) || !isBSTree(node->right))
      return 0;
   return 1;
}
int findlargestBSTSize(struct node *root) {
   if (isBSTree(root)){
      return findTreeSize(root);
}
else
   return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
   node *root = new node(5);
   root->left = new node(2);
   root->right = new node(8);
   root->left->left = new node(1);
   root->left->right = new node(4);
   cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
   return 0;
}

आउटपुट

The size of the largest possible BST is 5

एक और तरीका

समस्या का एक अन्य समाधान पेड़ को नीचे से पार करना और यह जांचना है कि क्या यह अपने बच्चे के नोड्स का उपयोग करके बीएसटी है। इस नोड के लिए, हम ट्रैक करेंगे

अगर यह बीएसटी है या नहीं।

  • बाएँ सबट्री के मामले में अधिकतम तत्व का मान।

  • सही सबट्री के मामले में न्यूनतम तत्व। BST की जाँच के लिए इन मानों की वर्तमान नोड से तुलना करने की आवश्यकता है।

साथ ही, सबसे बड़े BST के आकार को वर्तमान BST आकार से जाँच कर अपडेट किया जाएगा।

उदाहरण

#include<bits/stdc++.h>
using namespace std;
class node{
   public:
   int data;
   node* left;
   node* right;
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
   if (node == NULL){
      *isBSTree = true;
      return 0;
   }
   int min = INT_MAX;
   bool left_flag = false;
   bool right_flag = false;
   int leftSubtreeSize,rightSubTreeSize;
   *maxValLsubTree = INT_MIN;
   leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
   if (*isBSTree == true && node->data > *maxValLsubTree)
      left_flag = true;
   min = *minValRsubTree;
   *minValRsubTree = INT_MAX;
   rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
   if (*isBSTree == true && node->data < *minValRsubTree)
      right_flag = true;
   if (min < *minValRsubTree)
      *minValRsubTree = min;
   if (node->data < *minValRsubTree)
      *minValRsubTree = node->data;
   if (node->data > *maxValLsubTree)
      *maxValLsubTree = node->data;
   if(left_flag && right_flag){
      if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
         *maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
      return (leftSubtreeSize + rightSubTreeSize + 1);
   }
   else{
      *isBSTree = false;
      return 0;
   }
}
int findlargestBSTSize(node* node){
   int min = INT_MAX;
   int max = INT_MIN;
   int largestBSTSize = 0;
   bool isBST = false;
   findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
   return largestBSTSize;
}
int main(){
   node *root = new node(5);
   root->left = new node(2);
   root->right = new node(8);
   root->left->left = new node(1);
   root->left->right = new node(4);
   cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
   return 0;
}

आउटपुट

The Size of the largest BST is 5

  1. पायथन में दिए गए बाइनरी ट्री में बीएसटी का सबसे बड़ा योग मूल्य खोजने का कार्यक्रम

    मान लीजिए कि हमें एक बाइनरी ट्री प्रदान किया जाता है। हमें यह पता लगाना होगा कि क्या इसके सबट्री में बाइनरी सर्च ट्री (BST) मौजूद हैं और सबसे बड़े BST का योग ज्ञात करें। योग का पता लगाने के लिए, हम उस BST में प्रत्येक नोड के मान जोड़ते हैं। हम योग मान को आउटपुट के रूप में लौटाते हैं। तो, अगर इनपुट

  1. पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा पूर्ण उपट्री खोजें

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इस बाइनरी ट्री में अधिकतम पूर्ण उप-वृक्ष का आकार खोजना होगा। जैसा कि हम जानते हैं कि एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है यदि सभी स्तर पूरी तरह से बिना संभावित अंतिम स्तर के भरे हुए हैं और अंतिम स्तर में यथासंभव सभी कुंजियाँ हैं। तो, अगर इनपुट पसंद है

  1. पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा परफेक्ट सबट्री खोजें

    मान लीजिए कि हमारे पास एक दिया गया बाइनरी ट्री है; हमें दिए गए बाइनरी ट्री में सबसे बड़े परफेक्ट उप-वृक्ष का आकार ज्ञात करना है। जैसा कि हम जानते हैं कि पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें सभी आंतरिक नोड्स में दो बच्चे होते हैं और सभी पत्ते समान स्तर पर होते हैं। तो, अगर इनपुट पसंद है तो