Chương trình duyệt cây nhị phân theo cấp độ (Level Order) trong C++

Cho một cây nhị phân. Duyệt cây theo thứ tự cấp độ (level order traversal).

Ví dụ: cây gốc 1, trái 2, phải 3, 2->phải 5, 3->phải 4 → kết quả: [1, 2, 3, 5, 4].

Thuật toán (BFS)

• Khởi tạo hàng đợi q, đẩy gốc vào.
• Khi hàng đợi không rỗng:
  • Lấy nút đầu node, in giá trị.
  • Đẩy con trái rồi con phải vào hàng đợi (nếu tồn tại).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

class Solution {
public:
    vector<int> solve(TreeNode* root) {
        if (!root) return {};
        vector<int> ret;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            ret.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return ret;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);

Đầu ra

[1, 2, 3, 5, 4, ]