모든 노드가 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