Duyệt cây Zig Zag theo cấp độ chỉ dùng một hàng đợi trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân. Nhiệm vụ là in ra thứ tự duyệt Zig Zag (xoắn ốc) theo cấp độ của cây. Đối với duyệt này, chúng ta chỉ sử dụng một hàng đợi (queue) duy nhất.

Ví dụ minh họa:

Kết quả -

3   1   7   2   8   9   5

Để giải quyết bài toán chỉ dùng một hàng đợi, chúng ta sẽ sử dụng một cờ phân tách (separation flag) thêm vào cùng với hàng đợi và cờ hướng (direction flag).

Chúng ta sẽ duyệt cây cấp độ bởi cấp độ, chèn nút gốc, sau đó với mỗi phần tử trong hàng đợi chèn các nút con của nó vào hàng đợi. Nếu gặp NULL, chúng ta sẽ kiểm tra hướng và duyệt các phần tử theo hướng đó. Tiếp tục chèn cho đến khi gặp NULL cuối cùng.

Chương trình minh họa

Chương trình minh họa giải pháp của chúng ta:

#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 << "Duyệt Zig Zag của cây là:\n"; 
    zigZagTraversal(root, 7); 
    return 0; 
}

Kết quả

Duyệt Zig Zag của cây là: 3   1   7   2   8   9   5