面试题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上:点我前往

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