এই টিউটোরিয়ালে, আমরা একটি আর্বিট্রারি বাইনারি ট্রিকে চাইল্ড্রেন সম প্রপার্টি ধারণকারী ট্রিতে কনভার্ট করার প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হলো সেটিকে সেই বাইনারি ট্রিতে কনভার্ট করা যা চাইল্ড্রেন সম প্রপার্টি মেনে চলে। কিন্তু রেস্ট্রিকশন হলো আমরা শুধু নোডগুলোর মান বাড়াতে পারব, নোডের মান কমাতে পারব না এবং ট্রির স্ট্রাকচার পরিবর্তন করতে পারব না।
C++ উদাহরণ
#include<iostream> #include<bits/stdc++.h> using namespace std; // বাইনারি ট্রি নোড স্ট্রাকচার class node{ public: int data; node* left; node* right; // নতুন নোড তৈরি node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; // লেফট সাবট্রি ইনক্রিমেন্ট করা void increment(node* node, int diff); // ট্রি কনভার্ট করার মূল ফাংশন void convert_Btree(node* node){ int left_data = 0, right_data = 0, diff; // রুট বা লিফ নোড হলে true রিটার্ন if (node == NULL || (node->left == NULL && node->right == NULL)) return; else { // লেফট এবং রাইট সাবট্রি কনভার্ট করা 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; // চাইল্ড্রেন সম বের করা diff = left_data + right_data - node->data; // যদি চাইল্ড্রেন সম নোড ডেটা থেকে বড় হয় if (diff > 0) node->data = node->data + diff; if (diff > 0) increment(node, -diff); } } // নোড মান ইনক্রিমেন্ট করা void increment(node* node, int diff){ if(node->left != NULL) { node->left->data = node->left->data + diff; // ট্রিতে রিকার্শিভলি যাওয়া increment(node->left, diff); } else if (node->right != NULL) { node->right->data = node->right->data + diff; increment(node->right, diff); } } // ইন-অর্ডার ট্রাভার্সাল প্রিন্ট করা 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
