面试题23：从上往下打印二叉树

题目：从上往下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如输入下图所示的二叉树，则依次打印出8,6,10,5,7,9,11.

二叉树的节点定义如下：

struct BinaryTreeNode
{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
    {}
}

---

分析

对二叉树而言，第n层最少有1个节点，最多有2^n-1个节点。很明显，要以层序打印二叉树，就要在遍历时将当前层的节点保存起来，目的有两个，一是为了遍历以当前层节点为跟的子树，二是为了打印这些节点。

二叉树的层序遍历在广义上可看成是一种“广度优先搜索”策略，由此我们联想的图算法中的广度优先搜索算法，采用“队列”这个数据结构。思想如下：

先将根节点放入队列，而后在循环中将队列的队首的左右子树放进队列。要注意的是，题目要求按从左到右的顺序打印，所以需要先push右子树，再push左子树。如此循环直到队列为空即可。

代码如下：

void PrintFromTopToBottom(BinaryTreeNode* root)
{
    if(root==NULL)
        return;
    queue<binarytreenode> q;
    q.push(root);
    while(!q.empty())
    {
        if(q.front()->left!=NULL)
            q.push(q.front()->left);
        if(q.front()->right!=NULL)
            q.push(q.front()->right);
        cout<<q.front->value<<" ";
        q.pop();
    }
    cout<<endl;
}
</q.front-></binarytreenode>```

**以上**

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：[点我前往](https://github.com/SmartBrave/Sword-to-Offer/blob/master/23_PrintBinaryTree/main.cpp)

<div>[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")</div>

??自为知笔记(Wiz)")</div>