C++ में BST को बाइनरी ट्री में बदलें ताकि प्रत्येक कुंजी में सभी बड़ी कुंजियों का योग जुड़ जाए

इस ट्यूटोरियल में, हम एक प्रोग्राम पर चर्चा करेंगे जो 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