এই টিউটোরিয়ালে, আমরা একটি 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
