এই সমস্যায়, আমাদের একটি ট্রি দেওয়া আছে এবং আমাদের কাজ হল রিকারশন ব্যবহার করে ট্রির সাইজ ক্যালকুলেট করার একটি প্রোগ্রাম তৈরি করা।
একটি ট্রির সাইজ হল ট্রিতে উপস্থিত মোট নোডের সংখ্যা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
উপরোক্ত ট্রির সাইজ ৫।
ট্রির সাইজ বের করতে, আমাদের লেফট সাবট্রি এবং রাইট সাবট্রির সাইজ যোগ করে ১ বাড়াতে হবে। রিকারসিভ ফাংশনটি ট্রির লেফট এবং রাইট সাবট্রি দুটোই কল হবে। এবং কোনো সাবট্রি না পেলে ০ রিটার্ন করবে।
উপরের উদাহরণ এই মেথড দিয়ে সমাধান
ট্রির সাইজ বের করতে,
size(3) = size(5) + size(7) + 1
size(3) = (size(1) + size(9) + 1) + 1 + 1
size(3) = (1 + 1 + 1) + 1 + 1
size(3) = 5
আমাদের সমাধানের কাজ করার পদ্ধতি ইলাস্ট্রেট করার প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int findSize(node* node) {
if (node == NULL)
return 0;
else
return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(7);
root->left->left = insertNode(1);
root->left->right = insertNode(5);
root->right->left = insertNode(2);
cout << "The size of the given tree is " << findSize(root);
return 0;
}
আউটপুট
The size of the given tree is 6
