इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य बाइनरी ट्री को जिगजैग रूप में प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
उपरोक्त बाइनरी ट्री का जिगजैग ट्रैवर्सल है
3 5 1 8 7 0 4
इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को लेवल दर लेवल ट्रैवर्स करना होगा। ट्रैवर्सल का क्रम प्रत्येक लेवल के बाद उल्टा हो जाएगा।
अब, हम दो स्टैक (करंट और नेक्स्ट) और ऑर्डर के लिए एक मान का उपयोग करेंगे। पहले, हम करंट से नोड को ट्रैवर्स करेंगे और लेफ्ट चाइल्ड से राइट चाइल्ड तक नोड्स को फीड करेंगे ताकि रिवर्स ऑर्डर मिले। फिर करंट से फिर रिवर्स करेंगे। ऑर्डर वेरिएबल यह दिखाने में महत्वपूर्ण भूमिका निभाता है कि किस साइड को प्रिंट करना है।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root) {
if (!root)
return;
stack<struct Node*> currentLevel;
stack<struct Node*> nextLevel;
currentLevel.push(root);
bool LtR = true;
while (!currentLevel.empty()) {
struct Node* temp = currentLevel.top();
currentLevel.pop();
if (temp) {
cout << temp->data << "\t";
if (LtR) {
if (temp->left)
nextLevel.push(temp->left);
if (temp->right)
nextLevel.push(temp->right);
} else {
if (temp->right)
nextLevel.push(temp->right);
if (temp->left)
nextLevel.push(temp->left);
}
}
if (currentLevel.empty()) {
LtR = !LtR;
swap(currentLevel, nextLevel);
}
}
}
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(5);
root->left->left = insertNode(8);
root->left->right = insertNode(7);
root->right->left = insertNode(0);
root->right->right = insertNode(4);
cout << "दिए गए बाइनरी ट्री का जिगजैग ट्रैवर्सल है \n";
zigZagTreeTraversal(root);
return 0;
}
आउटपुट
दिए गए बाइनरी ट्री का जिगजैग ट्रैवर्सल है 3 5 1 8 7 0 4
