এখানে আমরা দেখব কিভাবে একটি বাইনারি ট্রি সম-বৃক্ষ কিনা তা পরীক্ষা করা যায়। এখন প্রশ্ন হল সম-বৃক্ষ কি? একটি সম-বৃক্ষ হল একটি বাইনারি গাছ যেখানে একটি নোড তার সন্তানদের সমষ্টির মান ধরে রাখে। গাছের মূলে এর নীচে থাকা সমস্ত উপাদানের সম্পূর্ণ যোগফল থাকবে। এটি সম-বৃক্ষের একটি উদাহরণ -
এটি পরীক্ষা করার জন্য, আমরা একটি সহজ কৌশল অনুসরণ করব, আমরা বাম এবং ডান সাবট্রি উপাদানগুলির যোগফল খুঁজে পাব যদি যোগফলের মান মূলের সমান হয়, তবে সেটি হল যোগ-বৃক্ষ। এটি একটি পুনরাবৃত্তিমূলক পদ্ধতি হবে৷
৷উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left, *right;
};
int sum_of_nodes(node *root) {
if(root == NULL)
return 0;
return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
int left_sum, right_sum;
if(node == NULL || (node->left == NULL && node->right == NULL))
return 1;
left_sum = sum_of_nodes(node->left);
right_sum = sum_of_nodes(node->right);
if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
return 1;
return 0;
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(26);
root->left = getNode(10);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(6);
root->right->right = getNode(3);
if(isSumTree(root))
cout << "The tree is Sum Tree";
else
cout << "The tree is not a Sum Tree";
} আউটপুট
The tree is Sum Tree
