हमें इनपुट के रूप में एक बाइनरी ट्री दिया गया है। लक्ष्य इसके अंदर सबट्री के रूप में मौजूद बाइनरी सर्च ट्री (बीएसटी) की संख्या का पता लगाना है। BST एक बाइनरी ट्री है जिसमें बायां बच्चा जड़ से कम और दायां बच्चा जड़ से अधिक होता है।
उदाहरण के लिए
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count the Number of Binary Search Trees present in a Binary Tree are: 2
स्पष्टीकरण
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जाँच करेंगे कि इसमें कोई बाइनरी सर्च ट्री मौजूद है या नहीं। प्रत्येक रूट नोड बाइनरी सर्च ट्री का प्रतिनिधित्व करता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि कोई अन्य बाइनरी सर्च ट्री मौजूद नहीं है इसलिए गिनती 2 है जो एक बाइनरी ट्री में लीफ नोड्स की कुल संख्या है।
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count the Number of Binary Search Trees present in a Binary Tree are: 6
स्पष्टीकरण
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरीट्री बनाने के लिए किया जाता है और हम जांच करेंगे कि इसमें कोई बाइनरी सर्च ट्री मौजूद है या नहीं। प्रत्येक रूटनोड बाइनरी सर्च ट्री का प्रतिनिधित्व करता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि 4 लीफ नोड्स और दो सबट्री हैं जो बीएसटी बना रहे हैं इसलिए गिनती 6 है।
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम नोड के बाएं उपट्री में नोड का सबसे बड़ा मान पाएंगे और जांचेंगे कि क्या यह एन से कम है। साथ ही, हम नोड एन के दाएं उपट्री में सबसे छोटा मान पाएंगे और जांच करेंगे कि यह इससे अधिक है या नहीं N. यदि सही है, तो यह एक BST है। बाइनरी ट्री को बॉटम अप तरीके से पार करें और उपरोक्त शर्तों और BSTs की वृद्धि गणना की जाँच करें
-
प्रत्येक नोड_डेटा के नोड में बीएसटी की संख्या, उस पेड़ में अधिकतम मूल्य, न्यूनतम मूल्य, बूलियन सत्य जैसी जानकारी होती है यदि वह सबट्री एक बीएसटी है।
-
फ़ंक्शन बीएसटी_प्रेजेंट (स्ट्रक्चर ट्री_नोड * पैरेंट) माता-पिता पर निहित बाइनरी ट्री के अंदर मौजूद बीएसटी की संख्या का पता लगाता है।
-
अगर पैरेंट NULL है तो {0, min, max, true} लौटाएं जहां min INT-MIN है और मैक्स INT_MAX है।
-
यदि बाएँ और दाएँ बच्चे अशक्त हैं तो {1, माता-पिता-> डेटा, माता-पिता-> डेटा, सत्य}
लौटाएँ -
नोड_डेटा लेफ्ट =BST_वर्तमान (पैरेंट-> लेफ्ट) सेट करें; और नोड_डेटा राइट =बीएसटी_प्रेजेंट (पैरेंट−>राइट);
-
नोड n1 लें और n1.lowest =min(parent−>data, (min(Left.lowest,Right.lowest))) को इसके दाएं सबट्री में सबसे कम सेट करें।
-
सेट n1.highest =max(parent−>data, (max(Left.highest, right.highest))); इसके बाएं उप-वृक्ष में उच्चतम के रूप में।
-
if(Left.check &&Right.check &&parent−>data> left.highest &&parent−>data
-
bsts की संख्या n1.total_bst =1 + बाएँ.total_bst + Right.total_bst;
के रूप में बढ़ाएँ -
अन्यथा n1.check =false सेट करें और n1.total_bst =left.total_bst +Right.total_bst के रूप में गिनें।
-
अंत में वापसी n1.
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct tree_node{
struct tree_node* left;
struct tree_node* right;
int data;
tree_node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct node_data{
int total_bst;
int highest, lowest;
bool check;
};
node_data BST_present(struct tree_node* parent){
if(parent == NULL){
int max = INT_MAX;
int min = INT_MIN;
return { 0, min, max, true };
}
if(parent−>left == NULL){
if(parent−>right == NULL){
return { 1, parent−>data, parent−>data, true };
}
}
node_data Left = BST_present(parent−>left);
node_data Right = BST_present(parent−>right);
node_data n1;
n1.lowest = min(parent−>data, (min(Left.lowest, Right.lowest)));
n1.highest = max(parent−>data, (max(Left.highest, Right.highest)));
if(Left.check && Right.check && parent−>data > Left.highest && parent−>data < Right.lowest){
n1.check = true;
n1.total_bst = 1 + Left.total_bst + Right.total_bst;
} else{
n1.check = false;
n1.total_bst = Left.total_bst + Right.total_bst;
}
return n1;
}
int main(){
struct tree_node* root = new tree_node(3);
root−>left = new tree_node(7);
root−>right = new tree_node(4);
root−>left−>left = new tree_node(5);
root−>right−>right = new tree_node(1);
root−>left−>left−>left = new tree_node(10);
cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count the Number of Binary Search Trees present in a Binary Tree are: 2