Duyệt cây ZigZag 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 cây nhị phân dưới dạng ZigZag.

Ví dụ minh họa:

Duyệt ZigZag của cây nhị phân trên là:

3   5   1   8   7   0   4

Để giải quyết bài toán, chúng ta cần duyệt cây nhị phân cấp độ bởi cấp độ. Thứ tự duyệt sẽ được đảo ngược sau mỗi cấp độ.

Chúng ta sẽ sử dụng hai ngăn xếp (current và next) và một biến cho thứ tự. Đầu tiên, duyệt nút từ current và đưa các nút con từ trái sang phải để thứ tự ngược được trả về. Sau đó đảo ngược lại từ current. Biến thứ tự đóng vai trò quan trọng trong việc xác định bên nào được in.

Chương trình minh họa

Chương trình triển khai giải pháp:

#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 << "Duyệt ZigZag của cây nhị phân cho trước là \n"; 
    zigZagTreeTraversal(root); 
    return 0; 
}

Kết quả

Duyệt ZigZag của cây nhị phân cho trước là 3   5   1   8   7   0   4