더 큰 모든 키의 합이 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