从上往下打印二叉树

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解读： 

如下图所示，将所有节点按照题目要求打印出来，输出顺序是8、7、9、5、20、13、14，这里用到的数据结构是二叉树的广度优先搜索，即一层层的从左到右顺序识别每个节点。前面一篇博客文章提到了深度优先搜索，广度优先搜索会用到队列这个数据结构，而深度优先搜索会用到栈这个数据结构，其中对于广度优先搜索：弹出元素是搜索的元素顺序，首先使用的是当把一个节点压入队列中，然后弹出队列的对头元素，当弹出该对头元素后，然后把该对头元素的左右子节点，依次压入队列当中，不断循环下去，知道队列中没有元素为止即可输出二叉树的所有元素。

下面用队列的图解的方式解释了上述二叉树的优先搜索方案：

代码：

class solution{
	public:
		vector<int> BFS(TreeNode *root)
		{
			vector<int> result;//定义一个int型输出容器
			queue<TreeNode*> queue_bfs;//定义一个放置二叉树节点的队列
			//queue_bfs.push(root);
			queue_bfs.push(root);//首先把根节点放入栈中，作为第一个元素
			while(!queue_bfs.empty)
			{
				TreeNode *temp=queue_bfs.front();
				result.push_back(queue_bfs.front()->data);
				queue_bfs.pop();//弹出对头元素
                //先压入左子节点，后压入右子节点
				if(temp->left!=null)
				{
					queue_bfs.push(temp->left);//对应的放入上面队头元素的左节点
				}
				if(temp->right!=null)
				{
					queue_bfs.push(temp->right);//对应的放入上面队头元素的右节点
				}
			}
                        return result;
		}
}