임의의 이진 트리를 C++에서 하위 합계 속성을 보유하는 트리로 변환

이 튜토리얼에서는 임의의 이진 트리를 자식 합계 속성을 포함하는 트리로 변환하는 프로그램에 대해 설명합니다.

이를 위해 이진 트리가 제공됩니다. 우리의 임무는 그것을 children sum 속성을 따르는 이진 트리로 변환하는 것입니다. 그러나 제한 사항은 노드에 있는 값만 증가시킬 수 있으며 트리 구조를 변경하거나 노드의 값을 감소시킬 수 없다는 것입니다.

예시

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//node structure for binary tree
class node{
   public:
   int data;
   node* left;
   node* right;
   //creation of new node
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
//incrementing left subtree
void increment(node* node, int diff);
//main function converting the tree
void convert_Btree(node* node){
   int left_data = 0, right_data = 0, diff;
   //returning true in case of root
   //or leaf node
   if (node == NULL || (node->left == NULL &&
   node->right == NULL))
   return;
   else {
      //converting left and right subtrees
      convert_Btree(node->left);
      convert_Btree(node->right);
      if (node->left != NULL)
         left_data = node->left->data;
      if (node->right != NULL)
         right_data = node->right->data;
      //getting children sum
      diff = left_data + right_data - node->data;
      //if children sum is greater than node data
      if (diff > 0)
         node->data = node->data + diff;
      if (diff > 0)
         increment(node, -diff);
   }
}
//incrementing the node value
void increment(node* node, int diff){
   if(node->left != NULL) {
      node->left->data = node->left->data + diff;
      //moving recursively in the tree
      increment(node->left, diff);
   }
   else if (node->right != NULL) {
      node->right->data = node->right->data + diff;
      increment(node->right, diff);
   }
}
//printing inorder traversal
void printInorder(node* node){
   if (node == NULL)
      return;
   printInorder(node->left);
   cout<<node->data<<" ";
   printInorder(node->right);
}
int main(){
   node *root = new node(50);
   root->left = new node(7);
   root->right = new node(2);
   root->left->left = new node(3);
   root->left->right = new node(5);
   root->right->left = new node(1);
   root->right->right = new node(30);
   cout << "Before conversion: " << endl;
   printInorder(root);
   convert_Btree(root);
   cout << "\nAfter conversion: " << endl;
   printInorder(root);
   return 0;
}

출력

Before conversion:
3 7 5 50 1 2 30
After conversion:
14 19 5 50 1 31 30