ইনপুট হিসাবে একটি বাইনারি গাছ এবং একটি মান 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