Chuyển cây nhị phân tùy ý thành cây có tính chất tổng con (Children Sum Property) trong C++

Cho cây nhị phân, chuyển thành cây thỏa mãn Children Sum Property: giá trị nút = tổng giá trị 2 con. Chỉ được tăng giá trị nút, không được giảm hay thay đổi cấu trúc.

Ví dụ:

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

Giải pháp: Post-order traversal. Tính tổng 2 con. Nếu tổng > nút cha, tăng nút cha. Nếu tổng < nút cha, tăng con (đệ quy).

Chương trình minh họa

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class node{
public:
    int data;
    node* left;
    node* right;
    node(int data){ this->data = data; left = right = NULL; }
};
void increment(node* node, int diff);
void convert_Btree(node* node){
    int left_data = 0, right_data = 0, diff;
    if (!node || (!node->left && !node->right)) return;
    convert_Btree(node->left);
    convert_Btree(node->right);
    if (node->left) left_data = node->left->data;
    if (node->right) right_data = node->right->data;
    diff = left_data + right_data - node->data;
    if (diff > 0) node->data += diff;
    if (diff < 0) increment(node, -diff);
}
void increment(node* node, int diff){
    if(node->left){
        node->left->data += diff;
        increment(node->left, diff);
    } else if (node->right){
        node->right->data += diff;
        increment(node->right, diff);
    }
}
void printInorder(node* node){
    if (!node) 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 << "Trước chuyển đổi: "; printInorder(root);
    convert_Btree(root);
    cout << "\nSau chuyển đổi: "; printInorder(root);
    return 0;
}

Kết quả

Trước chuyển đổi: 3 7 5 50 1 2 30
Sau chuyển đổi: 14 19 5 50 1 31 30