พิมพ์ระดับของ Binary Tree เรียงจากน้อยไปมากใน C++

โจทย์

ให้ Binary Tree ต้องการพิมพ์โหนดในแต่ละระดับ (Level) เรียงจากน้อยไปมาก

วิธีแก้ปัญหา

ใช้ BFS (Queue) ร่วมกับ Priority Queue (Min-Heap) 2 ตัว:

• Queue สำหรับ BFS ทั่วไป
• current_level: Min-heap เก็บค่าระดับปัจจุบัน
• next_level: Min-heap เก็บค่าระดับถัดไป
• ใช้ NULL เป็นตัวแบ่งระดับ

ตัวอย่างโค้ด C++

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

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

void printLevelElements(Node* root) {
    if (root == NULL) return;
    queue<Node*> q;
    priority_queue<int, vector<int>, greater<int> > current_level;
    priority_queue<int, vector<int>, greater<int> > next_level;
    q.push(root);
    q.push(NULL);
    current_level.push(root->data);
    while (!q.empty()) {
        int data = current_level.top();
        Node* node = q.front();
        if (node == NULL) {
            q.pop();
            if (q.empty()) break;
            q.push(NULL);
            cout << "\n";
            current_level.swap(next_level);
            continue;
        }
        cout << data << " ";
        q.pop();
        current_level.pop();
        if (node->left != NULL) {
            q.push(node->left);
            next_level.push(node->left->data);
        }
        if (node->right != NULL) {
            q.push(node->right);
            next_level.push(node->right->data);
        }
    }
}

Node* insertNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    Node* root = insertNode(12);
    root->left = insertNode(98);
    root->right = insertNode(34);
    root->left->left = insertNode(76);
    root->left->right = insertNode(5);
    root->right->left = insertNode(12);
    root->right->right = insertNode(45);
    cout << "Elements at each Level of binary tree are \n";
    printLevelElements(root);
    return 0;
}

ผลลัพธ์

Elements at each Level of binary tree are
12
34 98
5 12 45 76