इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम पेड़ के ज़िगज़ैग लेवल ऑर्डर ट्रैवर्सल को प्रिंट करना है। इस ट्रैवर्सल के लिए, हम केवल एक ही कतार का उपयोग करेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
आउटपुट -
3 1 7 2 8 9 5
एकल कतार का उपयोग करके इस समस्या को हल करने के लिए, हम कतार और दिशा ध्वज के साथ एक अतिरिक्त पृथक्करण ध्वज का मुकदमा करेंगे।
अब, हम पेड़ के स्तर को स्तर से पार करेंगे, रूट तत्व डालें, अब कतार के प्रत्येक तत्व के लिए सम्मिलित करें अपने बच्चे के नोड को कतार में डालें। यदि NULL का सामना करना पड़ता है, तो हम दिशा की जांच करेंगे और फिर दिए गए दिशा में तत्वों को पार करेंगे। फिर हम तब तक सम्मिलित करते रहेंगे जब तक हम अंतिम NULL पर नहीं जाते।
उदाहरण
हमारे समाधान को दर्शाने के लिए प्रोग्राम,
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
void zigZagTraversal(struct Node* root, int n){
struct Node* queue[2 * n];
int top = -1;
int front = 1;
queue[++top] = NULL;
queue[++top] = root;
queue[++top] = NULL;
int prevFront = 0, count = 1;
while (1) {
struct Node* curr = queue[front];
if (curr == NULL) {
if (front == top)
break;
else {
if (count % 2 == 0) {
for (int i = prevFront + 1; i < front; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = front - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
prevFront = front;
count++;
front++;
queue[++top] = NULL;
continue;
}
}
if (curr->left != NULL)
queue[++top] = curr->left;
if (curr->right != NULL)
queue[++top] = curr->right;
front++;
}
if (count % 2 == 0) {
for (int i = prevFront + 1; i < top; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = top - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(7);
root->left->left = insertNode(5);
root->left->right = insertNode(9);
root->right->left = insertNode(8);
root->right->right = insertNode(2);
cout<<"Zig Zag traversal of the tree is :\n";
zigZagTraversal(root, 7);
return 0;
} आउटपुट
Zig Zag traversal of the tree is : 3 1 7 2 8 9 5