os.walk() 或等效的 Python 函数中是否有“广度优先”搜索选项？

Question

示例目录树：

     root
     /|\
    / | \
   /  |  \
  A   B   C
     /     \
    /       \
   D         E
              \
               \
                F
                 \
                  \
                   G

os.walk() 将使用深度优先搜索算法遍历这个目录树。例如，os.walk() 将按以下顺序处理这棵树：root、A、B、D、C、E、F、G。os.walk() 似乎没有提供广度优先的选项搜索。如果此选项可用，它将按以下顺序处理这棵树：root、A、B、C、D、E、F、G。在我的应用程序中，我需要进行反向搜索。然而， os.walk(tree, topdown = False) 产生：A、D、B、G、F、E、C、根。相反，反向广度优先搜索将产生：G、F、E、D、C、B、A、根。

我必须创建自己的解决方案，如下所示：

def reversewalk(path):
    dirlist = {}
    for dirName, subdirList, fileList in os.walk(path, topdown=False):
        depth = dirName.count(os.path.sep)
        dirlist[os.path.abspath(dirName)] = (depth, dirName, subdirList, fileList)
    return sorted(dirlist.items(), key = lambda x : x[1], reverse = True)

我的问题是：在 os.walk() 或等效的 Python 函数中是否有“广度优先”搜索选项？后续问题是：如果没有，是否有比我提出的更好的解决方案？

Answer 1

以下代码来自我读过的一篇ActiveState文章：

#!/usr/bin/env python
import os

# -------------------------------------------
def breadthFirstFileScan( root ) :
    dirs = [root]
    # while we has dirs to scan
    while len(dirs) :
        nextDirs = []
        for parent in dirs :
            # scan each dir
            for f in os.listdir( parent ) :
                # if there is a dir, then save for next ittr
                # if it  is a file then yield it (we'll return later)
                ff = os.path.join( parent, f )
                if os.path.isdir( ff ) :
                    nextDirs.append( ff )
                else :
                    yield ff
        # once we've done all the current dirs then
        # we set up the next itter as the child dirs 
        # from the current itter.
        dirs = nextDirs

# -------------------------------------------
# an example func that just outputs the files.
def walkbf( path ) :
    for f in breadthFirstFileScan( path ) :
        print f

# ============================================
# as a demo we'll just start from where we 
# were called from.
walkbf( os.getcwd() )