এই টিউটোরিয়ালে আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি বাইনারি ট্রিকে এমনভাবে রূপান্তর করে যাতে প্রতিটি নোড তার ডান সাবট্রির সব নোডের যোগফল সংরক্ষণ করে।
এখানে একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হল একটি অন্য ট্রি রিটার্ন করা যেখানে প্রতিটি নোড অবশ্যই সেই নোড এবং তার ডান সাবট্রির যোগফলের সমান হবে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// ট্রির নোড স্ট্রাকচার
struct Node {
int data;
Node *left, *right;
};
// নতুন নোড তৈরি
struct Node* createNode(int item) {
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// নতুন বাইনারি ট্রি তৈরি
int rightsum_tree(Node* root) {
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
// বাম/ডান সাবট্রির মান পরিবর্তন
int rightsum = rightsum_tree(root->right);
int leftsum = rightsum_tree(root->left);
// ডান সাবট্রির যোগফল যোগ করা
root->data += rightsum;
return root->data + leftsum;
}
// ট্রি ইনঅর্ডার প্যাটার্নে ট্রভার্স
void inorder(struct Node* node) {
if (node == NULL)
return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
int main() {
struct Node* root = NULL;
root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);
rightsum_tree(root);
cout << "Updated Binary Tree:\n";
inorder(root);
return 0;
}
আউটপুট
Updated Binary Tree: 4 7 5 10 9 6
