学步园

如果只是分层遍历二叉树并打印出所有元素，那么使用队列来实现BFS是最好的选择。

但是这里要求，每层元素打印为一行，所以我们必须知道每层元素的开始和结束是什么，这种情况下，使用数组或者vector容器是更好的选择，使用两个变量来标识每一层的开始和结束，控制每一层元素的访问。代码如下：

/*
 * 分层打印二叉树，每层一行
 * */

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

struct Node
{
        int data;
        Node *left;
        Node *right;
};

vector<Node *> vec;


//如果是普通的分层遍历二叉树，只要求把序列打印出来
//用队列是最好的选择
//但是这里要每一层分行打印，就需要增加标识一层开始
//和结束的标志了，因此用vector或数组比较合适
void TravelByLevel(Node *root)
{
        if(root == NULL)
                return;
        
        vec.push_back(root);
        int cur = 0;
        int last = 1;

        while(cur < vec.size()){

                last = vec.size();
                //一层的开始
                while(cur < last){
                        cout << vec[cur] << " ";
                        if(vec[cur]->left != NULL){
                                vec.push_back(vec[cur]->left);
                        }
                        if(vec[cur]->right != NULL){
                                vec.push_back(vec[cur]->right);
                        }
                        cur++;
                }
                cout << endl;
        }               
}

如果要求自叶子节点到根，分层打印出每层节点呢？

此时上面的方法将不适用，因为上面的方法，在遍历的同时，vector也在自适应地往后生长，符合自根向叶子遍历的方向。

可以在每一层之间加一个标识来解决这个问题，比如使用NULL来分隔每一层。同时左右孩子节点加入vector的顺序决定了遍历的时候是从左往右还是从右往左。

/*
 * 自底向上分层访问二叉树节点
 * */

#include <iostream>
using namespace std;

struct Node
{
        int data;
        Node *left;
        Node *right;
};

vector<Node *> vec;

//direction控制节点访问的顺序是从左向右还是从右向左
void PrintNodeByLevel(Node *root, int direction)
{
        if(root == NULL)
                return;

        vec.push_back(root);
        int cur = 0;
        int last;

        while(cur < vec.size()){
                last = vec.size();
                vec.push_back(NULL);
                while(cur < last){
                        //每层访问的顺序从右向左
                        if(direction){
                                if(vec[cur]->left != NULL){
                                        vec.push_back(vec[cur]->left);
                                }
                                if(vec[cur]->right != NULL){
                                        vec.push_back(vec[cur]->right);
                                }
                        //每层访问的顺序从左向右
                        }else{
                                if(vec[cur]->right != NULL){
                                        vec.push_back(vec[cur]->right);
                                }
                                if(vec[cur]->left != NULL){
                                        vec.push_back(vec[cur]->left);
                                }
                        }
                        cur++;
                }
                //跳过NULL
                cur++;
        }

        //反向遍历，输出结果
        for(vector<Node *>::iterator iter = vec.rbegin(); iter != vec.rend(); ++iter){
                if(*iter == NULL){
                        cout << endl;
                }else{
                        cout << (*iter)->data << " "; 
                }
        }               
}