Binary Tree

---

Binary tree layer by layer traversal

针对二叉树的宽度优先遍历(Width first traversal)

现在的二叉树

• 需要打印成
• 1
• 2 3
• 4 5 6
• 7 8 这种情况

last:表示正在打印的当前行的最右节点. nlast:表示下一行的最右节点.

last用来换行
nlast记录着刚进入队列的节点,目前的下一层的最右节点 我们需要用队列来解决这个问题

它的解决步骤是:

令last=节点1
将节点1放入队列中,弹出节点1并打印完毕
此时把节点1的孩子依次放入queue中.
令nlast=node2
nalast=node3 意思就是谁进入队列,nlast就记录谁. node3 node2
----------->
此时发现弹出的node1与last相等,此时换行.

此时nlast在node3上, 再从queue弹出node2,并打印 把node2的孩子node4放入queue中,令nlast=node4,弹出节点3,并打印.

把node3的孩子依次放入queue,放入node5时,nlast=node5,放入node6时,nlast=node6, 此时发现弹出的node3已经是last节点了,所以换行.

令last=nlast last变为node6,last成功的变成了下一行的最右节点.

当某一节点走到last层的时候,说明这一层打印完毕,需要打印换行.

接下来,让last等于当前行的last,正确的找到下一层的最右节点,从而完成换行.