एक बाइनरी ट्री और एक मान x इनपुट के रूप में दिया गया है। लक्ष्य बाइनरी ट्री के उन सभी सबट्री को ढूंढना है जिनके नोड्स के वजन का योग x के बराबर है।
उदाहरण के लिए
इनपुट
x = 14. मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है

आउटपुट
Count of subtrees that sum up to a given value x are: 1
व्याख्या
हमें x मान 14 के रूप में दिया गया है। जैसा कि हम देख सकते हैं केवल एक लीफ नोड है जिसका मान 14 है इसलिए गिनती 1 है।
इनपुट
x = 33. मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count of subtrees that sum up to a given value x are: 2
व्याख्या
हमें x मान 33 के रूप में दिया गया है। जैसा कि हम देख सकते हैं दो सबट्री हैं जिनके योग मान 33 हैं इसलिए गिनती 2 है।


नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम रिकर्सिवली रूट नोड के बाएं सबट्री और दाएं सबट्री के वजन का योग गणना करेंगे और अंत में हम इसे रूट के वजन में जोड़ देंगे। यदि योग x के बराबर है तो गिनती बढ़ाएं।
रूट के पॉइंटर के साथ एक ट्री Tree_Node बनाएं।
फ़ंक्शन insert_Node(int data) इस ट्री में नोड्स जोड़ता है।
फ़ंक्शन subtrees_x(Tree_Node* root, int x) ट्री के रूट पॉइंटर और x लेता है और दिए गए मान x तक योग करने वाले सबट्री की संख्या लौटाता है।
एक स्टैटिक वेरिएबल count को 0 के रूप में लें क्योंकि हम रिकर्सिवली गिनती की गणना करेंगे।
Tree_node टाइप का एक स्टैटिक नोड लें जैसे root।
वेरिएबल Left_subtree = 0, Right_subtree = 0 इनिशियलाइज़ करें। रूट से बाएं और दाएं सबट्री में नोड्स के वजन के योग के लिए।
यदि रूट NULL है, तो योग 0 के रूप में लौटाएं।
बाएं सबट्री में नोड्स के योग के लिए Left_subtree += subtrees_x(root->Left, x) की गणना करें।
दाएं सबट्री में नोड्स के योग के लिए Right_subtree += subtrees_x(root->Right, x) की गणना करें।
sum = Left_subtree + Right_subtree + root->data सेट करें।
यदि योग x के बराबर है तो count बढ़ाएं।
यदि temp != root, स्टार्ट नोड नहीं है, तो योग को Left_subtree + root->data + Right_subtree के रूप में लौटाएं।
- अंत में count को लौटाएं जैसे नोड्स के योग 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