C++二叉树层次遍历（BFS）实现：队列打印与序列化

准备条件

实现二叉树的层次遍历主要依赖以下组件：

• STL 队列：<queue>，用于暂存待处理的节点，遵循先进先出（FIFO）原则。
• 树节点结构体：包含整型数值和左右子节点指针。
• 迭代逻辑：逐层处理当前队列中的所有节点，将下一层节点入队。

第1步：定义树节点

构建基础的 TreeNode 结构，初始化时设置其值，并将左/右指针设为空。

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    // 构造函数简化初始化
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

第2步：实现 BFS 层次遍历打印

目标是对二叉树进行层级访问并依次输出节点值。核心思路是利用变量记录每一层的节点数量（sz），确保每次只处理同一层级的节点。

// 迭代打印层次遍历
void BFSTraverse(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root); // 根节点入队
    
    while (!nodeQueue.empty()) {
        int sz = nodeQueue.size(); // 记录当前层节点数
        for (int i = 0; i < sz; i++) {
            TreeNode* node = nodeQueue.front();
            cout << node->val << ", ";
            nodeQueue.pop();
            
            if (node->left)
                nodeQueue.push(node->left);
            if (node->right)
                nodeQueue.push(node->right);
        }
        cout << endl; // 每层结束换行
    }
}

第3步：实现树结构的字符串序列化

除了打印，常需将树转化为扁平化的字符串以便存储或传输。本例采用前序逻辑结合占位符的方式：#!代表空节点，其他节点拼接值和感叹号。

// 按照节点顺序序列化成一个字符串
string serialByBFS(TreeNode* root) {
    if (root == nullptr)
        return "#!";
    
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    string res;
    
    while (!nodeQueue.empty()) {
        int sz = nodeQueue.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = nodeQueue.front();
            nodeQueue.pop();
            
            if (node) {
                res += to_string(node->val) + '!';
                // 即使是空节点也要放入队列以维持结构完整性
                nodeQueue.push(node->left);
                nodeQueue.push(node->right);
            } else {
                res += "#!";
            }
        }
    }
    return res;
}

第4步：测试用例与运行结果

构建如下结构的二叉树进行测试：

• 根节点: 5
• 左子: 3 (子: 1, 2)
• 右子: 8 (子: 4, 5 -> 左孙6, 9->右孙11)

int main() {
    TreeNode* head = new TreeNode(5);
    head->left = new TreeNode(3);
    head->right = new TreeNode(8);
    head->left->left = new TreeNode(1);
    head->left->right = new TreeNode(2);
    head->right->left = new TreeNode(4);
    head->right->right = new TreeNode(5);
    head->right->left->left = new TreeNode(6);
    head->right->right->left = new TreeNode(9);
    head->right->right->right = new TreeNode(11);

    cout << "traverse result:";
    BFSTraverse(head);
    cout << "\nserialized binary:";
    string res = serialByBFS(head);
    cout << res << endl;
    return 0;
}

控制台将依次输出各层级的节点ID以及序列化后的长字符串。

简要总结

通过 std::queue 控制访问顺序，可以有效解决二叉树的层次遍历问题。关键在于利用循环前的 size() 操作来区分层级边界。以上就是 C++ 实现二叉树版本层次遍历功能的详细内容，更多关于 C++ 数据结构与算法的资料请关注本站其它相关文章！