基于向量实现的树的广度优先遍历：员工层级打印疑问

嘿，我来帮你理清这个问题！首先明确你的核心困惑：队列应该存储单个Employee对象（或者更高效的指针/引用），而不是vector<Employee>。BFS的本质是按层级逐个处理每个节点（这里每个员工就是一个节点），队列的作用是记录当前层级待处理的所有员工，处理完当前层的所有成员后，再推进到下一层。

先看看你现有代码里的几个问题：

• 外层的while(1)是死循环，程序永远不会终止
• 没有打印根节点e，直接开始打印下属了
• 没有按层级分组打印，你的代码会把所有下属混在一起输出，没法实现每一层一行的效果
• 原Employee类的成员函数getName()和getSubordinates()的const修饰位置不对，正确写法应该把const放在函数末尾，这样才能在const上下文里调用这些函数

修正后的完整实现 #

首先先把Employee类的函数声明和实现修正好：

#include <iostream>
#include <string>
#include <vector>
#include <queue>

class Employee {
public:
    // 修正const位置：成员函数的const放在末尾，返回值用const引用避免不必要的拷贝
    const std::string& getName() const {
        return name;
    }
    const std::vector<Employee>& getSubordinates() const {
        return subordinates;
    }

    // 给个构造函数方便创建员工对象
    Employee(std::string empName) : name(std::move(empName)) {}

    // 添加下属的方法，方便构建层级结构
    void addSubordinate(Employee subordinate) {
        subordinates.push_back(std::move(subordinate));
    }

private:
    std::string name;
    std::vector<Employee> subordinates;
};

然后是正确的printEmployeeLevels函数：

void printEmployeeLevels(const Employee& root) {
    // 用指针存储避免拷贝大对象，更高效；如果员工对象很小，也可以直接存Employee
    std::queue<const Employee*> employeeQueue;
    employeeQueue.push(&root);

    while (!employeeQueue.empty()) {
        // 关键：先获取当前层级的员工数量，确保我们一次性处理完当前层的所有成员
        int currentLevelSize = employeeQueue.size();
        
        // 遍历当前层级的所有员工
        for (int i = 0; i < currentLevelSize; ++i) {
            const Employee* currentEmp = employeeQueue.front();
            employeeQueue.pop();

            // 打印当前员工的名字
            std::cout << currentEmp->getName() << " ";

            // 将当前员工的所有下属加入队列，作为下一层级的待处理对象
            for (const auto& sub : currentEmp->getSubordinates()) {
                employeeQueue.push(&sub);
            }
        }
        // 当前层级打印完毕，换行
        std::cout << "\n";
    }
}

测试一下你的示例结构 #

int main() {
    // 构建你描述的层级：e -> a、b；a -> c、d；b -> f；c -> g
    Employee e("e");
    Employee a("a");
    Employee b("b");
    Employee c("c");
    Employee d("d");
    Employee f("f");
    Employee g("g");

    c.addSubordinate(g);
    a.addSubordinate(c);
    a.addSubordinate(d);
    b.addSubordinate(f);
    e.addSubordinate(a);
    e.addSubordinate(b);

    printEmployeeLevels(e);
    return 0;
}

运行结果 #

e 
a b 
c d f 
g 

几个关键点再强调下 #

• 队列存的是指向Employee的指针，这样可以避免拷贝整个对象，尤其是当员工对象包含更多数据时，效率提升很明显；如果只是简单的示例，存Employee对象也没问题，但指针更优。
• 必须先获取当前层级的员工数量，这是实现按层级换行的核心——这样我们能确保每次循环处理的都是同一层的所有员工，处理完就换行。
• 修正const修饰符的位置是必要的，否则当你把const Employee&传入函数时，调用getName()会编译报错。

内容的提问来源于stack exchange，提问作者smith1453