इस समस्या में हमें एक पूर्ण बाइनरी ट्री दिया जाता है। हमारा काम एक पूर्ण बाइनरी ट्री के मिरर इमेज नोड्स के योग को एक क्रम में खोजने के लिए एक प्रोग्राम बनाना है।
यहां, हमें बाएं सूर्य-पेड़ के इनऑर्डर ट्रैवर्सल को ढूंढना है, और फिर प्रत्येक नोड के लिए, हम इसके साथ दर्पण छवि जोड़ देंगे। इसका मतलब है कि अगर हम लेफ्ट लीफ नोड को ट्रेस कर रहे हैं, तो हम इसके साथ राइट लीफ नोड का मान जोड़ देंगे। चूंकि यह मिरर इमेज नोड है।
कुछ महत्वपूर्ण परिभाषाएं
पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जहां अंतिम स्तर को छोड़कर सभी स्तरों में नोड्स की संख्या सबसे अधिक होती है।
इनऑर्डर ट्रैवर्सल एक ट्री ट्रैवर्सल तकनीक है जिसमें पहले लेफ्ट सबट्री को विजिट किया जाता है, रूट को विजिट किया जाता है और राइट सब-ट्री को विजिट किया जाता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
आउटपुट - 9 9 17 2
स्पष्टीकरण - बाएं सबट्री का इनऑर्डर ट्रैवर्सल 5-7-8-1 है।
सभी नोड्स को जोड़ने से इमेज मिरर हो जाएंगी।
5 + 4 = 9 7 + 2 = 9 8 + 9 = 17 1 + 1 = 2
इस समस्या को हल करने के लिए, हम इनऑर्डर ट्रैवर्सल का उपयोग करके बाइनरी ट्री को पार करेंगे। हम दो नोड्स का उपयोग करेंगे, एक बाएं सबट्री को पार करने के लिए और दूसरा नोड के दर्पण पर जाने के लिए। उदाहरण के लिए, हमारे पास लेफ्ट सबट्री के लिए एक रूट नोड है और इसके लिए हमारे पास मिरररूट होगा जो इसकी मिरर इमेज को ट्रेस करेगा।
उदाहरण
समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#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<<"Sum of node and mirror image nodes are :\n";
printMirrorSum(root, root);
if (root)
cout<<(root->data + root->data);
return 0;
} आउटपुट
Sum of node and mirror image nodes are : 9 9 17 2