इनपुट के रूप में एक बाइनरी ट्री और एक मान x दिया गया है। लक्ष्य एक बाइनरी ट्री के सभी उपप्रकारों को खोजना है जिनके नोड्स के भार का योग x के बराबर है।
उदाहरण के लिए
इनपुट
x =14. मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है
आउटपुट
Count of subtrees that sum up to a given value x are: 1
स्पष्टीकरण
we are given with a x value as 14. As we can see there is only one leaf node with the values as 14 therefore the count is 1.
इनपुट
x =33. मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count of subtrees that sum up to a given value x are: 2
स्पष्टीकरण
we are given with a x value as 33. As we can see there are two subtrees with the sum values as 33 therefore the count is 2.
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम रूट नोड के बाएं सबट्री और राइट सबट्री के वजन के योग की गणना करेंगे और अंत में हम इसे रूट के वजन में जोड़ देंगे। यदि योग x के बराबर है तो वेतन वृद्धि की गणना करें।
-
एक पेड़ ट्री_नोड का निर्माण करें जिसकी जड़ इसकी जड़ के सूचक के रूप में हो।
-
फ़ंक्शन इन्सर्ट_नोड (इंट डेटा) इस ट्री में नोड्स जोड़ता है।
-
फ़ंक्शन subtrees_x(Tree_Node* root, int x) रूट पॉइंटर को ट्री और x तक ले जाता है और उप-ट्री की गिनती देता है जो किसी दिए गए मान x तक योग करता है।
-
एक स्थिर चर गणना को 0 के रूप में लें क्योंकि हम पुनरावर्ती रूप से गणना की गणना करेंगे।
-
ट्री_नोड प्रकार का एक स्थिर नोड रूट के रूप में लें।
-
प्रारंभिक चर लेफ्ट_सबट्री =0, राइट_सबट्री =0. रूट से लेफ्ट और राइट सबट्री में नोड के भार के योग के लिए।
-
यदि रूट NULL है, तो योग 0 के रूप में वापस करें।
-
लेफ्ट सबट्री में नोड्स के योग के लिए लेफ्ट_सबट्री + =सबट्री_एक्स (रूट−> लेफ्ट, एक्स) की गणना करें।
-
बाएं सबट्री में नोड्स के योग के लिए Right_subtree +=subtrees_x(root−>Right, x) की गणना करें।
-
सम =लेफ्ट_सबट्री + राइट_सबट्री + रूट−>एलडेटा सेट करें।
-
यदि योग x के बराबर है तो वेतन वृद्धि की गणना करें।
-
यदि अस्थायी!=रूट, प्रारंभ नोड नहीं है, तो वाम_सबट्री + रूट−>डेटा + राइट_सबट्री के रूप में योग लौटाएं।
-
अंत में वापसी की गणना पेड़ों की वांछित संख्या के रूप में की जाती है, जिसमें नोड का योग x के बराबर होता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
int data;
Tree_Node *Left, *Right;
};
Tree_Node* insert_Node(int data){
Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
new_node−>data = data;
new_node−>Left = new_node−>Right = NULL;
return new_node;
}
int subtrees_x(Tree_Node* root, int x){
static int count = 0;
static Tree_Node* temp = root;
int Left_subtree = 0, Right_subtree = 0;
if(root == NULL){
return 0;
}
Left_subtree += subtrees_x(root−>Left, x);
Right_subtree += subtrees_x(root−>Right, x);
int sum = Left_subtree + Right_subtree + root−>data;
if(sum == x){
count++;
}
if(temp != root){
int set = Left_subtree + root−>data + Right_subtree;
return set;
}
return count;
}
int main(){
Tree_Node* root = insert_Node(10);
root−>Left = insert_Node(20);
root−>Right = insert_Node(12);
root−>Left−>Left = insert_Node(14);
root−>Left−>Right = insert_Node(1);
root−>Right−>Left = insert_Node(21);
root−>Right−>Right = insert_Node(11);
int x = 14;
cout<<"Count of subtrees that sum up to a given value x are: "<<subtrees_x(root, x);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of subtrees that sum up to a given value x are: 1