分层遍历二叉树 并 分层处理

http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html 
书中没有提及，本问题其实是以广度优先搜索(breath-first search, BFS)去遍历一个树结构。广度优先搜索的典型实现是使用队列(queue)。其伪代码如下:

enqueue(Q, root)

do

    node = dequeue(Q)

    process(node) //如把内容列印

    for each child of node

        enqueue(Q, child)

while Q is not empty

书上的解法，事实上也使用了一个队列。但本人认为，使用vector容器，较不直觉，而且其空间复杂度是O(n)。

如果用队列去实现BFS，不处理换行，能简单翻译伪代码为C++代码:

void PrintBFS(Node* root) {

    queue<Node*> Q;

    Q.push(root);

    do {

        Node *node = Q.front();

        Q.pop();

        cout << node->data << " ";

        if (node->pLeft)

            Q.push(node->pLeft);

        if (node->pRight)

            Q.push(node->pRight);

    }

    while (!Q.empty());

}

本人觉得这样的算法实现可能比较清楚，而且空间复杂度只需O(m)，m为树中最多节点的层的节点数量。最坏的情况是当二叉树为完整，m = n/2。

之后的难点在于如何换行。

本人的尝试之一

第一个尝试，利用了两个队列，一个储存本层的节点，另一个储存下层的节点。遍历本层的节点，把其子代节点排入下层队列。本层遍历完毕后，就可换行，并交换两个队列。

void PrintNodeByLevel(Node* root) {

    deque<Node*> Q1, Q2;

    Q1.push_back(root);

    do {

        do {

            Node* node = Q1.front();

            Q1.pop_front();

            cout << node->data << " ";

            if (node->pLeft)

                Q2.push_back(node->pLeft);

            if (node->pRight)

                Q2.push_back(node->pRight);

        } while (!Q1.empty());

        cout << endl;

        Q1.swap(Q2);

    } while(!Q1.empty());

}

本实现使用deque而不是queue，因为deque才支持swap()操作。注意，swap()是O(1)的操作，实际上只是交换指针。

这实现要用两个循环(书上的实现也是)，并且用了两个队列。能够只用一个循环、一个队列么?

本人的尝试之二

换行问题其实在于如何表达一层的结束。书上采用了游标，而第一个尝试则用了两个队列。本人想到第三个可行方案，是把一个结束信号放进队列里。由于使用queue<Node*>，可以插入一个空指针去表示一层的遍历结束。

void PrintNodeByLevel(Node* root) {

    queue<Node*> Q;

    Q.push(root);

    Q.push(0);

    do {

        Node* node = Q.front();

        Q.pop();

        if (node) {

            cout << node->data << " ";

            if (node->pLeft)

                Q.push(node->pLeft);

            if (node->pRight)

                Q.push(node->pRight);

        }

        else if (!Q.empty()) {

            Q.push(0);

            cout << endl;

        }

    } while (!Q.empty());

}

这个实现的代码很贴近之前的PrintBFS()，也只有一个循环。注意一点，当发现空指针(结束信号)时，要检查队列内是否还有节点，如果没有的话还插入新的结束信号，则会做成死循环。