Zig Zag Level Order Traversal ของต้นไม้โดยใช้คิวเดียวใน C++

ในปัญหานี้ เราได้รับ binary tree งานของเราคือพิมพ์ zigzag level order traversal ของต้นไม้ สำหรับการท่องนี้ เราจะใช้คิวเพียงคิวเดียวเท่านั้น

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

ผลลัพธ์ -

3   1   7   2   8   9   5

เพื่อแก้ปัญหานี้โดยใช้คิวเดียว เราจะใช้ flag แยกเพิ่มเติมพร้อมกับคิวและ direction flag

ตอนนี้ เราจะท่องต้นไม้ระดับต่อระดับ ใส่ root element ตอนนี้สำหรับแต่ละองค์ประกอบของคิว ให้ใส่ child node ของมันเข้าไปในคิว หากพบ NULL เราจะตรวจสอบ direction แล้วท่ององค์ประกอบในทิศทางที่กำหนด จากนั้นเราจะยังคงใส่จนกว่าจะเยี่ยมชม 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