BST কে বাইনারি ট্রি-তে রূপান্তর যাতে সব বড় কি-এর যোগফল প্রতিটি কি-তে যোগ হয় C++-এ

এই টিউটোরিয়ালে আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি BST কে বাইনারি ট্রি-তে রূপান্তর করে যাতে সব বড় কি-এর যোগফল প্রতিটি কি-তে যোগ হয়।

এখানে একটি বাইনারি সার্চ ট্রি দেওয়া থাকবে। আমাদের কাজ হল সেই ট্রিকে একটি বাইনারি ট্রি-তে রূপান্তর করা যেখানে বর্তমান কি-তে সব বড় কি-এর যোগফল যোগ করা হবে। এটি দেওয়া BST-এর রিভার্স ইনঅর্ডার ট্রভারসাল এবং 그때まで সব পূর্ববর্তী উপাদানগুলির যোগফল রেখে অবশেষে বর্তমান উপাদানের সাথে যোগ করে করা হবে।

উদাহরণ

#include <bits/stdc++.h> 
using namespace std; 
// BST-এর নোড স্ট্রাকচার 
struct node { 
    int key; 
    struct node* left; 
    struct node* right; 
}; 
// কোনো চাইল্ড ছাড়া নতুন নোড তৈরি 
struct node* newNode(int key) { 
    struct node* node = (struct node*)malloc(sizeof(struct node)); 
    node->key = key; 
    node->left = NULL; 
    node->right = NULL; 
    return (node); 
} 
// BST-কে রিভার্স ইনঅর্ডারে ট্রভার্স করে যোগফল যোগ করা 
void reverse_BST(struct node* root, int* sum_ptr) { 
    if (root == NULL) 
        return; 
    reverse_BST(root->right, sum_ptr); 
    // পথে উপাদানগুলোর যোগফল 
    *sum_ptr = *sum_ptr + root->key; 
    root->key = *sum_ptr; 
    reverse_BST(root->left, sum_ptr); 
} 
// যোগফল ব্যবহার করে মান আপডেট করা 
void change_greater(struct node* root) { 
    int sum = 0; 
    reverse_BST(root, &sum); 
} 
// ইনঅর্ডার ট্রভার্সাল প্রিন্ট করা 
void printInorder(struct node* node) { 
    if (node == NULL) 
        return; 
    printInorder(node->left); 
    cout << node->key << " "; 
    printInorder(node->right); 
} 
int main() { 
    node* root = newNode(5); 
    root->left = newNode(2); 
    root->right = newNode(13); 
    cout << "Given Tree: " << endl; 
    printInorder(root); 
    change_greater(root); 
    cout << endl; 
    cout << "Modified Tree: " << endl; 
    printInorder(root); 
    return 0; 
}

আউটপুট

Given Tree: 2 5 13 
Modified Tree: 20 18 13