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