এই টিউটোরিয়ালে, আমরা একটি স্বেচ্ছাচারী বাইনারি ট্রিকে একটি গাছে রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব যা শিশুদের সমষ্টির সম্পত্তি ধারণ করে৷
এর জন্য আমাদের একটি বাইনারি গাছ দেওয়া হবে। আমাদের কাজ হল এটিকে বাইনারি ট্রিতে রূপান্তর করা যা শিশুদের সমষ্টি সম্পত্তি অনুসরণ করে। কিন্তু সীমাবদ্ধতা হল আমরা শুধুমাত্র নোডগুলিতে উপস্থিত মানগুলিকে বৃদ্ধি করতে পারি, গাছের গঠন পরিবর্তন করতে বা নোডে মানগুলি হ্রাস করতে পারি না৷
উদাহরণ
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//node structure for binary tree
class node{
public:
int data;
node* left;
node* right;
//creation of new node
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//incrementing left subtree
void increment(node* node, int diff);
//main function converting the tree
void convert_Btree(node* node){
int left_data = 0, right_data = 0, diff;
//returning true in case of root
//or leaf node
if (node == NULL || (node->left == NULL &&
node->right == NULL))
return;
else {
//converting left and right subtrees
convert_Btree(node->left);
convert_Btree(node->right);
if (node->left != NULL)
left_data = node->left->data;
if (node->right != NULL)
right_data = node->right->data;
//getting children sum
diff = left_data + right_data - node->data;
//if children sum is greater than node data
if (diff > 0)
node->data = node->data + diff;
if (diff > 0)
increment(node, -diff);
}
}
//incrementing the node value
void increment(node* node, int diff){
if(node->left != NULL) {
node->left->data = node->left->data + diff;
//moving recursively in the tree
increment(node->left, diff);
}
else if (node->right != NULL) {
node->right->data = node->right->data + diff;
increment(node->right, diff);
}
}
//printing inorder traversal
void printInorder(node* node){
if (node == NULL)
return;
printInorder(node->left);
cout<<node->data<<" ";
printInorder(node->right);
}
int main(){
node *root = new node(50);
root->left = new node(7);
root->right = new node(2);
root->left->left = new node(3);
root->left->right = new node(5);
root->right->left = new node(1);
root->right->right = new node(30);
cout << "Before conversion: " << endl;
printInorder(root);
convert_Btree(root);
cout << "\nAfter conversion: " << endl;
printInorder(root);
return 0;
} আউটপুট
Before conversion: 3 7 5 50 1 2 30 After conversion: 14 19 5 50 1 31 30
