इस ट्यूटोरियल में, हम एक मनमाना बाइनरी ट्री को एक ऐसे ट्री में बदलने के कार्यक्रम पर चर्चा करेंगे जिसमें चिल्ड्रन सम प्रॉपर्टी हो।
इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा काम इसे बाइनरी ट्री में बदलना है जो बच्चों की संपत्ति का अनुसरण करता है। लेकिन प्रतिबंध यह है कि हम केवल नोड्स में मौजूद मानों को बढ़ा सकते हैं, न तो पेड़ की संरचना को बदल सकते हैं और न ही नोड में घटते मानों को।
उदाहरण
#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
