Chuyển đổi Cây nhị phân tùy ý thành cây chứa Thuộc tính Sum Con trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi một cây nhị phân tùy ý thành một cây chứa thuộc tính sum con.

Đối với điều này, chúng tôi sẽ được cung cấp một cây nhị phân. Nhiệm vụ của chúng ta là chuyển nó thành cây nhị phân theo sau thuộc tính sum con. Nhưng hạn chế là chúng ta chỉ có thể tăng các giá trị có trong các nút, không thể thay đổi cấu trúc của cây hoặc giảm các giá trị trong nút.

Ví dụ

#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;
}

ĐẦU RA

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