bfs-norecursion.cpp

#include <iostream>
#include <queue>

struct TreeNode {
    int payload;
    TreeNode * left;
    TreeNode * right;
};

typedef std::queue<int> payload_queue;

TreeNode * new_node(int payload, TreeNode * left, TreeNode * right)
{
    TreeNode * node = new TreeNode;
    node->payload = payload;
    node->left = left;
    node->right = right;
    return node;
}

payload_queue traverse_tree_bfs2(TreeNode * root)
{
    int n;  // number of previous level items in the queue
    payload_queue values;

    std::queue<TreeNode*> queue;
    queue.push(root);
    n = 1;

    while (1) {
        if (n == 0) {
            break;
        }
        int tn = 0;
        for (int i=0; i<n; ++i) {
            TreeNode * node = queue.front();
            queue.pop();

            if (node->left != 0) {
                queue.push(node->left);
                ++tn;
            }
            if (node->right != 0) {
                queue.push(node->right);
                ++tn;
            }
            values.push(node->payload);
        }
        n = tn;
    }

    return values;
}

void print_payload_queue(payload_queue & values)
{
    while (!values.empty()) {
        int v = values.front();
        values.pop();
        std::cout << v << " ";
    }
    std::cout << std::endl;
}

int main()
{
    TreeNode * btree = new_node(1,
        new_node(2,
            new_node(4, 0, 0),
            new_node(5,
                new_node(7, 0, 0),
                new_node(8, 0, 0)
            )
        ),
        new_node(3,
            0,
            new_node(6,
                new_node(9, 0, 0),
                0
            )
        )
    );

    payload_queue values_bfs = traverse_tree_bfs2(btree);
    std::cout << "BFS (no recursion)" << std::endl;
    print_payload_queue(values_bfs);

    return 0;

}