非递归方式列出文件

Question

我有以下内容可以递归地列出目录中的文件：

import os

def listdir(dir):
    items = [dir + '/' + item for item in os.listdir(dir)]
    for item in items:
        if not os.path.isdir(item):
            print (item)
        else:
            listdir(item)

作为一种学术练习，我想看看如何将上述内容转换为无需递归的循环。这样做的例子是什么？到目前为止，我有一些类似的事情：

def listdir(dir):
    while True:
        items = os.listdir(dir)
        for item in items:
            if not is.path.isdir(item):
                print (item)
            else:
                 # ?
            

Answer 1

您可以使用 FIFO 队列（或等效的双端队列）：

def listdir(dir_initial):
    q = queue.Queue()
    q.put(dir_initial)

    while not q.empty():
        dir = q.get()
        items = os.listdir(dir)
        for item in items:
            item = dir + '/' + item
            if os.path.isdir(item):
                q.put(item)
            else:
                print(item)

如果我们遇到一个目录，我们会将其添加到队列中以供稍后处理。如果队列为空，我们就知道我们已经完成了。

请注意，这实现了广度优先搜索，而不是递归深度优先搜索，这意味着您将得到：

def listdir(dir_initial):
    q = queue.Queue()
    q.put(dir_initial)

    while not q.empty():
        dir = q.get()
        items = os.listdir(dir)
        for item in items:
            item = dir + '/' + item
            if os.path.isdir(item):
                q.put(item)
            else:
                print(item)

代替

/a/
/b/
/a/1/
/a/2/
/b/9/