二叉树的广度优先遍历

概念：

广度优先遍历（BFS）：对每一层结点一次访问，访问完一层进入下一层，并且每个节点只访问一次。
广度优先遍历树，需要用到队列（Queue）来存储节点对象，队列的特点就是先进先出（FIFO）。

针对上图用广度优先遍历过程如下：

（1） 首先将A节点插入队列中，队列中有元素（A）；
（2） 将A节点弹出 ，然后将A节点的左右节点依次插入队列，B在队首，C在队尾，队列中有元素（B,C）,此时得到A节点；
（3） 继续弹出队首元素，并将队首元素的左右节点插入队列，此时队列中有元素（C,D,E），得到节点B；
（4） 不断重复上述操作，直至队列中没有元素，则遍历完成。

python代码实现：

class Node(object):
    """初始化节点"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def BFS(root):
    res = []
    tmp = [root]
    if root==None:
        return res
    while tmp!=[]:
        res.append(root.val)#把首部的值放入结果中
        if root.left:#如果左孩子不为空
            tmp.append(root.left)
        if root.right:#如果右孩子不为空
            tmp.append(root.right)
        if not tmp:#如果队列中还有元素
            root = tmp.pop(0)
    return res

参考来源：

https://www.cnblogs.com/xiaolovewei/p/7763867.html