ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือพิมพ์ลำดับการข้ามผ่านของต้นไม้ระดับซิกแซก สำหรับการข้ามผ่านครั้งนี้ เราจะใช้คิวเดียวเท่านั้น
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ผลผลิต −
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
