将任意二叉树转换为包含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