C++实现二叉树的层序遍历

#include 
#include 
#include 
using namespace std;
struct TreeNode {
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int value, TreeNode *left, TreeNode *right)
    :value(value), left(left), right(right) {}
};
// 这里不考虑内存释放问题
class BinaryTree {
public:
    BinaryTree() {}

    void constructATree() {
        root = new TreeNode(1, nullptr, nullptr);
        root->left = new TreeNode(2, new TreeNode(3, nullptr, nullptr), new TreeNode(4, nullptr, nullptr));
        root->right = new TreeNode(5, new TreeNode(6, nullptr, nullptr), new TreeNode(7, nullptr, nullptr));
    }

    void bfs(function func) {
        auto q = queue();
        q.push(root);
        while(!q.empty()) {
            auto head = q.front();
            q.pop();
            func(head->value);

            if(head->left != nullptr) {
                q.push(head->left);
            }
            if(head->right != nullptr) {
                q.push(head->right);
            }
        }
    }
private:
    TreeNode *root;
};

int main(int argc, char *argv[]) {
    auto t = BinaryTree();
    t.constructATree();
    cout << "开始层序遍历(BFS)" << endl;
    t.bfs([=](int value) {
        cout << value << " -> ";
    });
    cout << endl << "遍历完毕" << endl;
    return 0;
}

编译运行

$ clang++ -o test 二叉树层序遍历.cxx -std=c++11
$ ./test

输出

开始层序遍历(BFS)
1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7 -> 
遍历完毕