इस समस्या में, हमें एक पूर्ण बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो पूर्ण बाइनरी ट्री के दर्पण छवि नोड्स का योग इनऑर्डर तरीके से निकाले।
यहां, हमें बाएं उप-ट्री का इनऑर्डर ट्रैवर्सल ढूंढना है, और फिर प्रत्येक नोड के लिए, हम उसके साथ दर्पण छवि जोड़ेंगे। इसका मतलब है यदि हम बाएं लीफ नोड को पार कर रहे हैं, तो हम उसके साथ दाएं लीफ नोड का मान जोड़ेंगे। क्योंकि यह दर्पण छवि नोड है।
कुछ महत्वपूर्ण परिभाषाएं
पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जहां अंतिम स्तर को छोड़कर सभी स्तरों में नोड्स की उच्चतम संख्या होती है।
इनऑर्डर ट्रैवर्सल एक ट्री ट्रैवर्सल तकनीक है जिसमें पहले बायां उप-ट्री देखा जाता है, फिर रूट देखा जाता है और फिर दायां उप-ट्री देखा जाता है।
आइए एक उदाहरण लेकर समस्या को समझते हैं,
इनपुट
आउटपुट - 9 9 17 2
व्याख्या - बाएं उप-ट्री का इनऑर्डर ट्रैवर्सल 5-7-8-1 है।
सभी नोड्स को दर्पण छवियों के साथ जोड़ना।
5 + 4 = 9 7 + 2 = 9 8 + 9 = 17 1 + 1 = 2
इस समस्या को हल करने के लिए, हम इनऑर्डर ट्रैवर्सल का उपयोग करके बाइनरी ट्री को पार करेंगे। हम दो नोड्स का उपयोग करेंगे, एक बाएं उप-ट्री को पार करने के लिए और दूसरा नोड के दर्पण को देखने के लिए। उदाहरण के लिए, हमारे पास बाएं उप-ट्री के लिए एक रूट नोड है और उसके लिए हमारे पास mirrorRoot होगा जो उसका दर्पण छवि पार करेगा।
उदाहरण
समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
typedef struct node {
int data;
struct node* left;
struct node* right;
node(int d) {
data = d;
left = NULL;
right = NULL;
}
} Node;
void printMirrorSum(Node* root, Node* rootMirror) {
if (root->left == NULL && rootMirror->right == NULL)
return;
printMirrorSum(root->left, rootMirror->right);
cout << (root->left->data + rootMirror->right->data) << endl;
printMirrorSum(root->right, rootMirror->left);
}
int main() {
Node* root = new Node(1);
root->left = new Node(7);
root->right = new Node(2);
root->left->left = new Node(5);
root->left->right = new Node(8);
root->right->left = new Node(9);
root->right->right = new Node(4);
cout << "नोड और दर्पण छवि नोड्स का योग:\n";
printMirrorSum(root, root);
if (root)
cout << (root->data + root->data);
return 0;
}
आउटपुट
नोड और दर्पण छवि नोड्स का योग: 9 9 17 2
