但是这个申请的Q的空间很大，一直往后面走

②叉树的层序遍历二叉树是面试经常会被考察的知识点，甚至要求当场写出实现过程

层序遍历二叉树所要解决的问题很好理解，就是按②叉树从上到下从左到右依次打印每个节点中存储的数据。如下图：

• 仔细看看层序遍历二叉树过程其实就是从上到下，從左到右依次将每个数放入到队列中然后按顺序依次打印就是想要的结果。

• 1、首先将二叉树的根节点push到队列中判断队列不为NULL，就输出隊头的元素
  2、判断节点如果有孩子，就将孩子push到队列中
  3、遍历过的节点出队列，
  

1、创建一个指针数组保存二叉树结构体指針，
2、保存二叉树根节点再申请变量 in、out ，控制数组在遍历过程中，始终能找到节点和该节点的前一个节点

层序遍历二叉树就是按二叉树从上到下，从左到右依次打印每个结点中存储的数据如上图层序遍历二叉树打印出来的就是1 2 3 4 5 6 7  8 9 10 11 12 13 14 15

2.层序遍历二叉树的的思想(我是这样来遍历的）

其实前 中 后 遍历都是栈的形式来打印，所以可以用遞归但是层序遍历二叉树不行，所以可以用队列来打印

  b.然后依次访问左右儿子(要先访问左儿子，在访问右儿子）

  c.如果左右儿子非空那么就加入队列

  d.一直到队列为空，结束访问