แปลง Binary Tree ตามอำเภอใจเป็นต้นไม้ที่มี Children Sum Property ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลงไบนารีทรีตามอำเภอใจเป็นทรีที่มีคุณสมบัติผลรวมย่อย

สำหรับสิ่งนี้เราจะได้รับไบนารีทรี งานของเราคือการแปลงเป็นไบนารีทรีที่ตามหลังคุณสมบัติผลรวมของลูก แต่ข้อจำกัดคือเราสามารถเพิ่มค่าที่มีอยู่ในโหนดเท่านั้น ไม่สามารถเปลี่ยนโครงสร้างของต้นไม้หรือค่าที่ลดลงในโหนดได้

ตัวอย่าง

#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