BST বা বাইনারি সার্চ ট্রি হলো বাইনারি ট্রির একটি রূপ যেটিতে সমস্ত বাম নোড রুটের চেয়ে ছোট এবং সমস্ত ডান নোড রুটের চেয়ে বড় হয়। এই সমস্যায় আমরা একটি বাইনারি ট্রি নেব এবং প্রতিটি নোডে তার চেয়ে বড় সব মান যোগ করব। “BST-এ প্রতিটি নোডে বড় মান যোগ” সমস্যাটি সরলীকৃত হলো: একটি BST-এ প্রতিটি নোডের মান থেকে বড় সব নোডের মান যোগ করা।
প্রবেশ:
10 / \ / \ 5 20 / \ / \ 1 7 1 5
আউটপুট
70 / \ 82 45 / \ / \ 83 77 60 25
ব্যাখ্যা
এই প্রোগ্রামটি একটি BST-কে একটি বাইনারি ট্রিতে রূপান্তর করবে যেখানে নোডের মান হবে সেটির চেয়ে বড় সব এলিমেন্টের যোগফল এবং নোডের মূল মান।
BST-এ প্রতিটি নোডে বড় মান যোগ করার সমাধান:
আমরা রিভার্স ইনঅর্ডার ট্রাভার্সাল ব্যবহার করব (রিকার্শন ডান সাবট্রি-তে প্রথমে কল হবে বাম সাবট্রি-র পরিবর্তে) এবং একটি ভেরিয়েবল রেখে ট্র্যাভার্স করা নোডগুলোর যোগফল রাখব।
তারপর এই যোগফল ব্যবহার করে বর্তমান নোডের মান পরিবর্তন করব, প্রথমে এর মান যোগফলে যোগ করব, তারপর নোডের মান এই যোগফল দিয়ে রিপ্লেস করব।
উদাহরণ
#include <iostream > using namespace std; struct node { int data; node *left; node *right; }; node *newNode(int key) { node *temp=new node; temp->left=NULL; temp->right=NULL; temp->data=key; return temp; } void Inorder(node *root) { if(!root) return; Inorder(root->left); cout<<root->data<<" "; Inorder(root->right); } node *Insert(node *root,int key) { if(!root) return newNode(key); if(key<root->data) root->left=Insert(root->left,key); else root->right=Insert(root->right,key); return root; } void RevInorderAdd(node *root,int &sum) { if(!root) return; RevInorderAdd(root->right,sum); sum+=root->data; root->data=sum; RevInorderAdd(root->left,sum); } void AddGreater(node *root) { int sum=0; RevInorderAdd(root,sum); } int main() { /* নিচের BST তৈরি করা হচ্ছে 10 / \ 5 20 / \ / \ 1 7 15 25 */ node *root = NULL; root = Insert(root, 10); Insert(root, 20); Insert(root, 25); Insert(root, 15); Insert(root, 5); Insert(root, 7); Insert(root, 1); Inorder(root); cout<<endl; AddGreater(root); Inorder(root); cout<<endl; return 0; }
