すべての大きいキーの合計がC++のすべてのキーに追加されるように、BSTをバイナリツリーに変換します

このチュートリアルでは、すべての大きいキーの合計がすべてのキーに追加されるように、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