[面試算法]Python實作用隊列對二叉樹進行廣度優先周遊(Breadth First Search, BFS)

導言

曾經面試遇到一道算法題，面試題如下：

如果要用掃描出某個目錄下的所有檔案夾和所有檔案，目錄深度為3，要求一層一層輸出，怎麼做？

這道題，當時面試的時候思考了幾秒鐘，想到無論是Linux目錄結構，還是Windows單分區目錄結構，都可以看做是一棵樹。

Linux

當中還有

tree

這樣的指令輸出目錄樹，還能限定深度。目錄樹是一顆多叉樹，類似二叉樹，肯定可以用二叉樹廣度優先搜尋的方法去做。思考了一會，便進行了回答：

目錄的結構是一顆樹，是一顆多叉樹，樹當中的每個節點代表着一個檔案夾或具體檔案，如果是檔案，一定是葉子節點；如果是目錄，一定是非葉子節點。可以采用廣度優先周遊的方式去掃描，還能限定掃描的深度。廣度優先周遊從根節點開始，先将根節點入隊列，之後循環擷取隊列第一個元素，出隊列并列印這個元素。如果這個節點有子節點，則子節點入隊列（多個子節點入隊列的順序按照需要進行，可以按照節點的屬性，例如檔案大小、檔案名等）。循環上述過程，直到隊列為空，結束。

這道題考察的是廣度優先周遊，是二叉樹廣度優先周遊的一個應用，多叉樹和二叉樹沒有質的差別。

二叉樹的廣度優先周遊

二叉樹或多叉樹沒有本質差別，我們以二叉樹為例進行讨論。廣度優先周遊(

Breadth First Search, BFS

)，又叫層次優先周遊。給定一棵二叉樹如下圖所示：

廣度優先周遊是層次周遊，逐層進行，第一層是根節點

A

，周遊結束之後周遊第二層，

B C

，然後周遊第三層

D E F

，最後周遊第四層

G

。

我們需要一個隊列（先進先出的資料結構），用于保證層次周遊，還需要一個結果數組存儲周遊的結果。

1. 初始化，如下圖左側。擷取隊首節點

   A

   并出隊列，加入到結果數組當中。節點

   A

   有左右子節點

   B

   和

   C

   ，将它們先後入隊列（

   B

   先入隊列，

   C

   後入隊列，這是保證從左到右的次序），如下圖右側所示。

   

2. 如下圖左側。擷取隊首節點

   B

   并出隊列，加入到結果數組當中。節點

   B

   有左右子節點

   D

   和

   E

   ，将它們入隊列，如下圖右側所示。

   

3. 如下圖左側。擷取隊首節點

   C

   并出隊列，加入到結果數組當中。節點

   C

   隻有右子節點

   F

   ，将

   F

   入隊列，如下圖右側所示。

   

4. 如下圖左側。擷取隊首節點

   D

   并出隊列，加入到結果數組當中。節點

   D

   沒有子節點則不進行其他操作，如下圖右側所示。

   

5. 如下圖左側。擷取隊首節點

   E

   并出隊列，加入到結果數組當中。節點

   E

   有左子節點

   G

   ，将

   G

   入隊列，如下圖右側所示。

   

6. 如下圖左側。擷取隊首節點

   F

   并出隊列，加入到結果數組當中。節點

   F

   沒有子節點則不進行其他操作。

   

7. 如下圖左側。擷取隊首節點

   G

   并出隊列，加入到結果數組當中。節點

   G

   沒有子節點則不進行其他操作。

   

8. 如下圖左側。隊列為空，退出。結果數組就是BFS的結果。

   

Python實作基于隊列的廣度優先周遊

Python代碼如下：

# 節點的資料結構
# val表示值、left表示目前節點的左子節點位址、right表示右子節點位址
class Node(object):
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right


# 二叉樹的廣度優先周遊
def bfs(root):
    result = []
    if root == None:
        return result
    queue = [root]
    while len(queue) > 0:
        head = queue[0]     # 擷取隊首元素
        queue.remove(head)  # 隊首元素出隊列
        result.append(head)
        if head.left != None:
            queue.append(head.left) # 左子節點入隊
        if head.right != None:      # 右子節點入隊
            queue.append(head.right)
    return result


if __name__ == "__main__":
    # 先建構二叉樹
    node7 = Node('G', None, None)
    node5 = Node('E', node7, None)
    node4 = Node('D', None, None)
    node2 = Node('B', node4, node5)
    node6 = Node('F', None, None)
    node3 = Node('C', None, node6)
    node1 = Node('A', node2, node3)

    result = bfs(node1)			# 廣搜
    print([x.val for x in result])
           

運作結果如下：

['A', 'B', 'C', 'D', 'E', 'F', 'G']

Process finished with exit code 0
           

結語

隊列(

First In Fistr Out, FIFO

)這種資料結構，看似簡單，比棧簡單多了，但卻在計算機當中有着神奇的作用，例如

BFS

要用隊列，

Dijkstra

算法使用優先隊列降低了時間複雜度，程序排程算法要用到多級隊列，基于

Zookeeper

的分布式鎖使用了類似隊列的概念保證了公平性，用于資料傳輸解耦的

Message Queue

也是隊列思想的最重要應用之一。