将任意二叉树转换为包含C ++中的Children Sum属性的树

在本教程中，我们将讨论将任意二叉树转换为具有子代sum属性的树的程序。

为此，我们将提供一个二叉树。我们的任务是将其转换为跟随子代sum属性的二叉树。但是限制是我们只能增加节点中存在的值，而不能改变树的结构或减少节点中的值。

示例

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//二叉树的节点结构
class node{
   public:
   int data;
   node* left;
   node* right;
   //创建新节点
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
//递增左子树
void increment(node* node, int diff);
//转换树的主要功能
void convert_Btree(node* node){
   int left_data = 0, right_data = 0, diff;
   //如果是root，则返回true-
   //或叶节点
   if (node == NULL || (node->left == NULL &&
   node->right == NULL))
   return;
   else {
      //转换左右子树
      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;
      //让孩子求和
      diff = left_data + right_data - node->data;
      //如果子项总和大于节点数据
      if (diff > 0)
         node->data = node->data + diff;
      if (diff > 0)
         increment(node, -diff);
   }
}
//增加节点值
void increment(node* node, int diff){
   if(node->left != NULL) {
      node->left->data = node->left->data + diff;
      //在树中递归移动
      increment(node->left, diff);
   }
   else if (node->right != NULL) {
      node->right->data = node->right->data + diff;
      increment(node->right, diff);
   }
}
//打印顺序遍历
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