面试题32_2：分行从上到下打印二叉树

分行从上到下打印二叉树（其实就是广度优先遍历），引用辅助队列。

不管是广度优先遍历一幅有向图还是一棵树，都要用到队列。首先把起始节点（对树而言是根节点）放入队列。接下来每次从队列的头部取出一个节点，遍历这个节点之后把它能到达的节点（对树而言是子节点）都依次放入队列。重复这个遍历过程，知道队列中的节点全部被遍历完为止。

C++版本

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
using namespace std;

queue<TreeNode *> queueTreeNode;

void Printf(TreeNode* root){
    if(root == nullptr)
        return ;
    int nextLevel = 0;
    int toBePrinted = 1;
    queueTreeNode.push(root);
    while(queueTreeNode.size() > 0){
        TreeNode* pNode = queueTreeNode.front();
        cout<<pNode->val<<" ";
        queueTreeNode.pop();
        if(pNode->left != nullptr){
            queueTreeNode.push(pNode->left);
            nextLevel++;
        }
        if(pNode->right != nullptr){
            queueTreeNode.push(pNode->right);
            nextLevel++;
        }
        toBePrinted--;
        if(toBePrinted == 0){
            cout<<endl;
            toBePrinted = nextLevel;
            nextLevel = 0;
        }
    }
}

int main()
{
    TreeNode* pNode8 = CreateBinaryTreeNode(8);
    TreeNode* pNode6 = CreateBinaryTreeNode(6);
    TreeNode* pNode10 = CreateBinaryTreeNode(10);
    TreeNode* pNode5 = CreateBinaryTreeNode(5);
    TreeNode* pNode7 = CreateBinaryTreeNode(7);
    TreeNode* pNode9 = CreateBinaryTreeNode(9);
    TreeNode* pNode11 = CreateBinaryTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    printf("====Test1 Begins: ====
");
    printf("Expected Result is:
");
    printf("8 
");
    printf("6 10 
");
    printf("5 7 9 11 

");

    printf("Actual Result is: 
");
    Printf(pNode8);
    printf("
");

    DestroyTree(pNode8);

    return 0;
}