Python程序：使用BFS遍历显示树的节点

二叉树是一种重要的数据结构，在计算机科学中被广泛应用。通常我们需要遍历一棵二叉树，通常有两种遍历方式：深度优先遍历和广度优先遍历。本篇文章将介绍如何使用BFS（Breadth-First Search）遍历显示树的节点，使用Python代码实现。

更多Python相关文章，请阅读：Python 教程

二叉树的定义及构建

首先来看二叉树的定义：

二叉树（Binary Tree）是一种树形结构，它的每个节点最多只有两个子节点。

接下来，我们使用Python定义一个二叉树，其中二叉树的节点由一个类来实现。该类有三个属性：左子节点、右子节点和节点的值。其中，左子节点、右子节点应该分别是一个Node类型的对象。

class Node:
    def __init__(self, value = None):
        self.left = None
        self.right = None
        self.value = value

定义一个二叉树：

def create_tree():
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    return root

BFS遍历算法

BFS遍历算法即广度优先遍历算法，其基本思想是：首先访问根节点，然后依次访问每层的节点，直到遍历完整个二叉树。

使用队列实现BFS遍历算法。我们将根节点加入一个队列中，然后从队列头部取出节点。将右、左子节点入队，直至队列为空。

Python代码

from queue import Queue

def BFS(root):
    if not root:
        return

    res = []
    q = Queue()
    q.put(root)

    while not q.empty():
        node = q.get()
        res.append(node.value)

        if node.left:
            q.put(node.left)

        if node.right:
            q.put(node.right)

    return res

上面的代码中，我们使用了Python内置的queue库中的Queue对象，它提供了线程安全的队列实现。在队列中，我们使用put()添加新节点，使用get()取出已有的节点，使用empty()判断队列是否为空。