学步园

问题来源：《编程之美》3.10 分层遍历二叉树

给定一棵二叉树，要求分层遍历该二叉树，即从上到下按层次访问该树，每一层单独输出一行，每一层要求访问的顺序为从左到右。

我们在遍历的过程中将该层节点的孩子节点压入一个队列，这样就可以实现从上到下一层一层地遍历该二叉树。

C++的程序描述如下：

void printNodeByLevel(BinTree root)
{
    if(root == NULL)
        return;

    vector<Node *> vec;
    vec.push_back(root);
    int cur = 0;
    int last = 1;

    while(cur < vec.size()) {
        last = vec.size();

        while(cur < last) {
            cout<<vec[cur]->data<<" ";

            if(vec[cur]->pLeft != NULL)
                vec.push_back(vec[cur]->pLeft);
            if(vec[cur]->pRight != NULL)
                vec.push_back(vec[cur]->pRight);

            ++cur;
        }

        cout<<endl;
    }
}

其中BinTree的定义如下：

typedef struct Node
{
    struct Node *pLeft;
    struct Node *pRight;
    int data;
}LNode, *BinTree;