แปลง Binary Tree ให้เป็น Tree ที่มี Children Sum Property ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง binary tree ให้เป็น tree ที่มี children sum property

สำหรับนี้ เราจะได้รับ binary tree งานของเราคือแปลงมันเป็น binary tree ที่ follow children sum property แต่มีข้อจำกัดคือเราสามารถเพิ่มค่าในโหนดได้เท่านั้น ไม่สามารถเปลี่ยนโครงสร้าง tree หรือลดค่าในโหนดได้

โปรแกรมตัวอย่าง

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// โครงสร้างโหนด binary tree
class node {
public:
    int data;
    node* left;
    node* right;
    // สร้างโหนดใหม่
    node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

// เพิ่มค่า left subtree
void increment(node* node, int diff);

// ฟังก์ชันหลักแปลง tree
void convert_Btree(node* node) {
    int left_data = 0, right_data = 0, diff;
    // return true ถ้าเป็น root หรือ leaf node
    if (node == NULL || (node->left == NULL && node->right == NULL))
        return;
    else {
        // แปลง left และ 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;
        // หา children sum
        diff = left_data + right_data - node->data;
        // ถ้า children sum มากกว่า 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;
        // ท่อง recursively ใน tree
        increment(node->left, diff);
    }
    else if (node->right != NULL) {
        node->right->data = node->right->data + diff;
        increment(node->right, diff);
    }
}

// พิมพ์ 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