ইনপুট হিসাবে একটি বাইনারি গাছ এবং একটি মান 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 এর সমান হয় তবে বৃদ্ধির সংখ্যা।
-
একটি ট্রি ট্রি_নোড তৈরি করুন রুট দিয়ে তার মূলের নির্দেশক হিসেবে।
-
ফাংশন insert_Node(int data) এই ট্রিতে নোড যোগ করে।
-
ফাংশন subtrees_x(Tree_Node* root, int x) রুট পয়েন্টারটিকে ট্রি andx-এ নিয়ে যায় এবং একটি প্রদত্ত মান x পর্যন্ত যোগ করা সাবট্রির সংখ্যা ফেরত দেয়।
-
একটি স্ট্যাটিক ভেরিয়েবল গণনাকে 0 হিসাবে নিন কারণ আমরা গণনা পুনরাবৃত্তভাবে গণনা করব।
-
রুট হিসাবে Tree_node টাইপের একটি স্ট্যাটিক নোড নিন।
-
ভেরিয়েবল শুরু করুন 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−>ldata.
সেট করুন। -
যদি যোগফল x এর সমান হয় তবে বৃদ্ধির সংখ্যা।
-
যদি temp!=root হয়, স্টার্ট নোড নয়, তাহলে যোগফল Left_subtree + root−>data + Right_subtree হিসাবে ফেরত দিন।
-
শেষে নোডের যোগফল 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
