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