इस ट्यूटोरियल में, हम एक मनमाने बाइनरी ट्री को चिल्ड्रन सम प्रॉपर्टी वाले ट्री में परिवर्तित करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक बाइनरी ट्री प्रदान की जाएगी। हमारा कार्य इसे उस बाइनरी ट्री में परिवर्तित करना है जो चिल्ड्रन सम प्रॉपर्टी का पालन करता है। लेकिन प्रतिबंध यह है कि हम केवल नोड्स में मौजूद मानों को बढ़ा सकते हैं, न तो ट्री की संरचना बदल सकते हैं और न ही नोड में मान घटा सकते हैं।
उदाहरण
#include<iostream> #include<bits/stdc++.h> using namespace std; //बाइनरी ट्री के लिए नोड संरचना class node{ public: int data; node* left; node* right; नया नोड बनाना node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; //बाएं उपट्री को बढ़ाना void increment(node* node, int diff); //ट्री परिवर्तित करने का मुख्य फ़ंक्शन void convert_Btree(node* node){ int left_data = 0, right_data = 0, diff; रूट या लीफ नोड के मामले में सच वापस करना if (node == NULL || (node->left == NULL && node->right == NULL)) return; else { //बाएं और दाएं उपट्री को परिवर्तित करना 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; //चिल्ड्रन सम प्राप्त करना diff = left_data + right_data - node->data; //यदि चिल्ड्रन सम नोड डेटा से बड़ा है if (diff > 0) node->data = node->data + diff; if (diff > 0) increment(node, -diff); } } //नोड मान बढ़ाना void increment(node* node, int diff){ if(node->left != NULL) { node->left->data = node->left->data + diff; //ट्री में रिकर्सिवली आगे बढ़ना increment(node->left, diff); } else if (node->right != NULL) { node->right->data = node->right->data + diff; increment(node->right, diff); } } //इनऑर्डर ट्रैवर्सल प्रिंट करना 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
