एक बीएसटी को एक बाइनरी ट्री में कनवर्ट करें जैसे कि सी ++ में प्रत्येक कुंजी में सभी बड़ी चाबियों का योग जोड़ा जाता है

इस ट्यूटोरियल में, हम एक BST को बाइनरी ट्री में बदलने के लिए एक प्रोग्राम पर चर्चा करेंगे जैसे कि सभी बड़ी कुंजियों का योग प्रत्येक कुंजी में जोड़ा जाता है।

इसके लिए हमें एक बाइनरी सर्च ट्री प्रदान किया जाएगा। हमारा काम उस पेड़ को एक बाइनरी ट्री में बदलना है, जिसमें वर्तमान कुंजी में सभी बड़ी कुंजियों को जोड़ा गया है। यह पिछले सभी तत्वों का योग होने और अंत में इसे वर्तमान तत्व में जोड़ने के साथ दिए गए BST के क्रम में रिवर्स द्वारा किया जाएगा।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//node structure of BST
struct node{
   int key;
   struct node* left;
   struct node* right;
};
//creating new node with no child
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);
}
//traversing BST in reverse inorder and adding sum
void reverse_BST(struct node *root, int *sum_ptr){
   if (root == NULL)
      return;
   reverse_BST(root->right, sum_ptr);
   //adding elements along the way
   *sum_ptr = *sum_ptr + root->key;
   root->key = *sum_ptr;
   reverse_BST(root->left, sum_ptr);
}
//Using sum and updating the values
void change_greater(struct node *root){
   int sum = 0;
   reverse_BST(root, &sum);
}
//printing inorder traversal
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