面试题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个节点,最多有2n-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>