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

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

二叉树的节点定义如下:

1
2
3
4
5
6
7
8
struct BinaryTreeNode
{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
{}
}


分析

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

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

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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void PrintFromTopToBottom(BinaryTreeNode* root)
{
if(root==NULL)
return;
queue<binarytreenode> q;
q.push(root);
while(!q.empty())
{
if(q.front()-&gt;left!=NULL)
q.push(q.front()-&gt;left);
if(q.front()-&gt;right!=NULL)
q.push(q.front()-&gt;right);
cout&lt;<q.front->value&lt;&lt;" ";
q.pop();
}
cout&lt;&lt;endl;
}
</q.front-></binarytreenode>

以上

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

完整代码及测试用例在github上:点我前往

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