任意の二分木をC++でChildrenSumプロパティを保持するツリーに変換します

このチュートリアルでは、任意の二分木を子の合計プロパティを保持するツリーに変換するプログラムについて説明します。

このために、バイナリツリーが提供されます。私たちのタスクは、それを子の合計プロパティに従う二分木に変換することです。ただし、制限は、ノードに存在する値のみをインクリメントでき、ツリーの構造を変更したり、ノードの値をデクリメントしたりすることはできないということです。

例

#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