แปลง Binary Tree เพื่อให้ทุกโหนดเก็บผลรวมของโหนดทั้งหมดในทรีย่อยที่ถูกต้องใน C++

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

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
//node structure of tree
struct Node {
   int data;
   Node *left, *right;
};
//creation of a new node
struct Node* createNode(int item){
   Node* temp = new Node;
   temp->data = item;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
//creating the new binary tree
int rightsum_tree(Node* root){
   if (!root)
      return 0;
   if (root->left == NULL && root->right == NULL)
      return root->data;
   //changing the values of left/right subtree
   int rightsum = rightsum_tree(root->right);
   int leftsum = rightsum_tree(root->left);
   //adding the sum of right subtree
   root->data += rightsum;
   return root->data + leftsum;
}
//traversing tree in inorder pattern
void inorder(struct Node* node){
   if (node == NULL)
      return;
   inorder(node->left);
   cout << node->data << " ";
   inorder(node->right);
}
int main(){
   struct Node* root = NULL;
   root = createNode(1);
   root->left = createNode(2);
   root->right = createNode(3);
   root->left->left = createNode(4);
   root->left->right = createNode(5);
   root->right->right = createNode(6);
   rightsum_tree(root);
   cout << "Updated Binary Tree :\n";
   inorder(root);
   return 0;
}

ผลลัพธ์

Updated Binary Tree :
4 7 5 10 9 6