广度优先搜索应用实例—温室大棚

在一个温室大棚中种有西红柿。该温室大棚使用种植架来种植西红柿,并使用人造光来照射西红柿。在种植架上的西红柿果实以二叉树的结构排列,二叉树的节点代表西红柿,二叉树的链接代表茎。

不幸的是,温室大棚两侧的照射灯只有右侧的工作,而左侧的灯因某些原因无法使用。种植人员在准备收获西红柿时才发现这些问题。检查后发现,因为光的接受度不够,只有每一层种植架上最右侧的西红柿正常成熟,可以食用。现给出种植架上西红柿的二叉树结构,求如果在上述情况下,有多少西红柿是成熟的。

从问题的描述中我们可以知道,在这道题中我们可以用广度优先搜索算法来处理树结构的图。二叉树结构已经在深度优先搜索算法中详细提及,这里不再赘述。但我们还需提及一下二叉树的性质:二叉树的任意一个节点下最多有两个分支;任意一个节点下的分支数量可能为 0、1、2,因此一个节点有可能有 0 个、1 个或 2 个子节点。图 1 和图 2 所示为二叉树结构的示例。
温室大棚西红柿分布示例图(1)
图 1:温室大棚西红柿分布示例图(1)
温室大棚西红柿分布示例图(2)
图 2:温室大棚西红柿分布示例图(2)

对于图 1 所示的二叉树结构来说,光只从右侧照射,因此能成熟的西红柿只有最右侧的节点 1、节点 3、节点 6、节 点7(图 1 中标为灰色的节点)。其余的节点均被其他西红柿挡住了光线。而对于图 2 的二叉树结构来说,只有节点 1、节点 3、节点 5、节点 6 为成熟的西红柿,可以被食用。

至此,我们可以用更简洁的语言来诠释本题的核心:寻找二叉树每一层中最右侧的节点。

为了不重不漏地寻找到所有成熟的西红柿,我们可以采用广度优先搜索算法来解决此问题:按照从根节点到底端叶子节点的顺序,找出可以获取的节点的值的问题。

在遍历之前,最重要的是定义二叉树图结构,因为本题关联到二叉树的结构,我们需要定义一个二叉树类型来存储二叉树上节点的数值和节点与节点的关系。与第6章我们介绍的二叉树结构一样,对每一个节点均定义三个属性:该节点的编号或值,该节点的左子节点的状态和该节点右子节点的状态。

具体代码如下:
class treenode:        #定义二叉树的根节点为TreeNode
    def __init__(self, val):
        self.val = val      #定义二叉树的每个元素的值,这里表示西红柿的编号
        self.left = None     #定义二叉树的每个元素的左子节点
        self.right = None    #定义二叉树的每个元素的右子节点

其次,我们需要对二叉树进行分层,因为只有分层之后才能准确地对每一层的节点进行遍历,寻找到最右边的节点。

通过广度优先搜索算法,我们可以根据其层次性取出每一层的数据,然后把每层的结果(最右边的节点)加入最终结果中。现在我们为每个节点设定一个层级,比如根节点的层级是第 1 层,根节点的子节点的层级是第 2 层,再往下的节点的层级依次递增,如图 3 所示。
温室大棚西红柿分层示例
图 3:温室大棚西红柿分层示例

这个题目可以说是二叉树广度优先搜索问题的一种变形,我们只需要将一整层放入队列,寻找到最右边的节点,再通过队列中的节点更新下一层的节点,将所有下一层的节点放入队列,并把前一层的节点移出队列,直到没有节点可以加入队列,队列为空为止。既然是广度优先搜索算法,那么一定要用到队列,使用队列来保存待处理的节点。

初始化时,首先处理根节点,存储根节点的值,同时建立存放结果的队列,这里的代码我们将用列表结构代替队列结构:
def bfs(root):
    mature = []          #存放结果数据,成熟的西红柿节点的编号
    queue = [root]         #队列存放待处理数据
    while len(queue) > 0:      #队列不为空时,依次取出数据作处理
        return mature

广度优先搜索算法代码的第一个核心是先取出每层的节点,然后处理该节点,之后把下一层的子节点都存入队列并移出上层已处理的节点,以此类推,直到队列为空,处理就完毕了。

为了保证广度优先搜索是一层层遍历,而不是按遍历的节点到根节点的距离的远近来遍历,需更新队列的时候加入一层 for 循环,保证这一层的节点均已用于更新下一层节点并已被移出队列。若 queue 队列中只包含一层的节点,那么 level_size 将为这一层节点的个数。在 for 循环中,这一层节点会依次被移出队列,同时用于更新下一层的子节点。

代码如下:
#queue为队列,top是一个treenode类型的变量
level_size = len(queue)
for i in range(level_size):
    top = queue.get()
    if top.left:
        queue.append(top.left)
    if top.right:
        queue.append(top.right)

广度优先搜索算法代码的第二个核心便是如何找到每层的最右边一个节点。为了最方便快捷地寻找到题目所要求的节点,建议使用 list 列表来模拟队列,而不是使用queue队列来直接实现。原因很简单:当一个队列只存储一层节点时,使用 list 列表可以直接访问队尾的节点,也就是该层最右边的节点,从而直接找到题目要求的答案,但 queue 队列不能进行该操作,queue 只能在更新队列时寻找到答案,需要通过烦琐的判断语句来判断遍历的节点是否为该层最后的节点,十分不便利。

现在将两步核心操作合并在一起:
def bfs(root):
    mature = []
    queue = [root]
    while queue:
        level_size = len(queue)
        mature.append(queue[-1].val)
        for i in range(level_size):
            top = queue.pop(0)
            if top.left:
                queue.append(top.left)
            if top.right:
                queue.append(top.right)
        return mature

之后便是建立二叉树的操作,题目的二叉树输入形式为:从根节点到叶子节点,从左叶子节点到右叶子节点依次输入,若该节点为空则输入“null”。比如图7-32所示二叉树的输入格式应为:
1 2 3 4 5 null 6 null null 7

为了满足遍历的需求,我们需要将每一个节点都转换为treenode属性,并找到每个节点的左子节点和右子节点(可以为空)。代码如下:
class treenode:            #定义treenode类型
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
Input = []               #Input列表用于存储输入
tree = []               #tree列表用于存储节点
Input = input().split()
cnt = 1
for item in Input:           #将所有节点转换为treenode类型
    tmp = treenode(item)
    tree.append(tmp)
for item in tree:
    if item.val == "null":       #若节点为“null”,则不加入tree中
        continue
    if 2 * cnt <= len(Input) and tree[2 * cnt - 1].val != "null":#找到每个节点的左子节点
        item.left = tree[2 * cnt - 1]
    if 2 * cnt + 1 <= len(Input) and tree[2 * cnt].val != "null":#找到每个节点的右子节点
        item.right = tree[2 * cnt]
    cnt += 1

整合上面的代码,呈现的完整代码如下:
class treenode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def bfs(root):
    mature = []
    queue = [root]
    while queue:
        level_size = len(queue)
        mature.append(queue[-1].val)
        for i in range(level_size):
            top = queue.pop(0)
            if top.left:
                queue.append(top.left)
            if top.right:
                queue.append(top.right)
    return mature
Input = []
tree = []
Input = input().split()
cnt = 1
for item in Input:
    tmp = treenode(item)
    tree.append(tmp)
for item in tree:
    if item.val == "null":
        continue
    if 2 * cnt <= len(Input) and tree[2 * cnt - 1].val != "null":
        item.left = tree[2 * cnt - 1]
    if 2 * cnt + 1 <= len(Input) and tree[2 * cnt].val != "null":
        item.right = tree[2 * cnt]
    cnt += 1
ans=bfs(tree[0])

当然,本题还有其他解法。比如可以改变遍历的顺序,即按先访问当前节点,再访问右节点,最后访问左节点的顺序。每次都将节点放进队列,但是在取节点的时候,只需记录第一个节点即可,其他的都可以释放掉,这个方法读者可以自己思考实现。