In các cấp cây nhị phân theo thứ tự tăng dần C++

Cho cây nhị phân. In các nút cùng cấp theo thứ tự giá trị tăng dần. Sử dụng queue cho BFS và 2 priority_queue (min-heap) cho cấp hiện tại và cấp tiếp theo. Dùng NULL phân cách cấp.

BFS + Priority Queue

Queue lưu nút, NULL đánh dấu hết cấp. 2 min-heap lưu giá trị cấp hiện tại và cấp sau. Khi gặp NULL, swap 2 heap, in xuống dòng.

Ví dụ minh họa

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

void printSortedLevels(Node* root) {
    if (!root) return;
    queue q;
    priority_queue, greater> cur, nxt;
    
    q.push(root);
    q.push(nullptr);
    cur.push(root->data);
    
    while (!q.empty()) {
        int val = cur.top();
        Node* node = q.front();
        
        if (!node) {
            q.pop();
            if (q.empty()) break;
            q.push(nullptr);
            cout << '\n';
            cur.swap(nxt);
            continue;
        }
        
        cout << val << ' ';
        q.pop();
        cur.pop();
        
        if (node->left) {
            q.push(node->left);
            nxt.push(node->left->data);
        }
        if (node->right) {
            q.push(node->right);
            nxt.push(node->right->data);
        }
    }
}

Node* newNode(int d) {
    Node* n = new Node();
    n->data = d; n->left = n->right = nullptr;
    return n;
}

int main() {
    Node* root = newNode(12);
    root->left = newNode(98);
    root->right = newNode(34);
    root->left->left = newNode(76);
    root->left->right = newNode(5);
    root->right->left = newNode(12);
    root->right->right = newNode(45);
    
    cout << "Cac cap sap xep:\n";
    printSortedLevels(root);
    return 0;
}

Kết quả

Cac cap sap xep:
12
34 98
5 12 45 76