এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হলো ট্রির জিগজ্যাগ লেভেল অর্ডার ট্রাভার্সাল প্রিন্ট করা, যেখানে শুধুমাত্র একটি কিউ ব্যবহার করতে হবে।
উদাহরণ:
আউটপুট -
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
