এখানে আমরা একটি रोचক সমস্যা দেখব, যেখানে একটি দেওয়া বাইনারি সার্চ ট্রি (BST)-এর প্রতিটি নোডে সেই নোডের চেয়ে বড় সব মান যোগ করা হবে। প্রারম্ভিক এবং চূড়ান্ত ট্রি নিচের মতো দেখাবে:
অ্যালগরিদম
bstUpdate(root, sum) −
শুরু যদি root নাল হয়, তবে থামুন bstUpdate(root-এর ডান পাশ, sum) sum := sum + root-এর মান root-এর মান sum দিয়ে আপডেট করুন bstUpdate(root-এর বাম পাশ, sum) শেষ
উদাহরণ
#include<iostream> using namespace std; class Node { public: int data; Node *left, *right; }; Node *getNode(int item) { Node *newNode = new Node(); newNode->data = item; newNode->left = newNode->right = NULL; return newNode; } void updateBST(Node *root, int *sum) { if (root == NULL) return; updateBST(root->right, sum); // ডান সাবট্রি আপডেট করুন *sum = *sum + root->data; root->data = *sum; // রুট ডেটা আপডেট করুন updateBST(root->left, sum); // বাম সাবট্রি আপডেট করুন } void BSTUpdate(Node *root) { int sum = 0; updateBST(root, &sum); } void inorder(Node *root) { if (root != NULL) { inorder(root->left); cout<<root->data<<" "; inorder(root->right); } } Node* insert(Node* node, int data) { if (node == NULL) return getNode(data); if (data <= node->data) // বামে যান node->left = insert(node->left, data); else // ডানে যান node->right = insert(node->right, data); return node; } int main() { int data[] = {50, 30, 20, 40, 70, 60, 80}; int n = sizeof(data)/sizeof(data[0]); Node *root = NULL; for(int i = 0; i < n; i++) { root = insert(root, data[i]); } BSTUpdate(root); inorder(root); }
আউটপুট
350 330 300 260 210 150 80
