इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम बाइनरी ट्री को ज़िगज़ैग रूप में प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
उपरोक्त बाइनरी ट्री का ज़िगज़ैग ट्रैवर्सल है
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 << "ZigZag traversal of the given binary tree is \n";
zigZagTreeTraversal(root);
return 0;
} आउटपुट
ZigZag traversal of the given binary tree is 3 5 1 8 7 0 4