漫步/遍历任意深度的嵌套字典（字典表示一个目录树）

Question

我几乎可以肯定有一个简单的解决方案，但我已经花了几个小时读取和重读相同的一组相关结果我很难回答我的问题。

这个问题的背景下（包括完成，但随意跳过此）

在此之前，因为我希望用户能够在一个目录内选择一组文件（以及任何子目录），不幸的是，在Windows 7（http://bugs.python.org/issue8010）中，Tkinter在文件对话框中选择多个文件的默认功能被破坏。因此，我试图通过替代方法（仍然使用Tkinter）来表示目录结构：构造目录结构的传真，由标记和缩进复选框（以树组织）组成。因此，像这样的目录：

\SomeRootDirectory 
    \foo.txt 
    \bar.txt 
    \Stories 
     \Horror 
      \rickscott.txt 
      \Trash 
       \notscary.txt 
     \Cyberpunk 
    \Poems 
     \doyoureadme.txt 

会是这个样子（其中＃代表checkbutton）：

SomeRootDirectory 
    # foo.txt 
    # bar.txt 
    Stories 
     Horror 
      # rickscott.txt 
      Trash 
       # notscary.txt 
     Cyberpunk 
    Poems 
     # doyoureadme.txt 

建立从目录结构中的原始字典很容易使用特定的食谱，我发现在ActiveState（见下文），但是当我尝试迭代我留下的很好的嵌套字典时，我碰到了一堵墙。我想我需要遍历它，以便用一个漂亮的树形网格表示来填充一个Tkinter框架。然后我希望通过解释哪些复选框是真的还是假的，来加载用户选择的各种文本文件。除了遍历字典而没有修复深度的以外，一切似乎都相当简单。

更抽象的术语

为了让我使用的是ActiveState的配方，这些嵌套的字典 - http://code.activestate.com/recipes/577879/。它实现os.walk来制作这样的字典：

a={ 
    'SomeRootDirectory': { 
     'foo.txt': None, 
     'bar.txt': None, 
     'Stories': { 
      'Horror': { 
       'rickscott.txt' : None, 
       'Trash' : { 
        'notscary.txt' : None, 
        }, 
       }, 
      'Cyberpunk' : None 
      }, 
     'Poems' : { 
      'doyoureadme.txt' : None 
     } 
    } 
} 

在这之后我就难住了。我是一个Python新手，仅仅是一个人文科学专业......在我看来，这意味着递归对我来说非常混乱。所以我查看了食谱，并尝试了各种类似的答案，但无济于事。我需要能够迭代这个字典，以便填充它的另一个表示形式，并且在这样做之后（即在用户选择了哪些文件之后）重建对这些文件的引用。

我很抱歉，如果这太冗长！感谢您的帮助！

解决方案改编自spicavigo的响应

#distinguish between directory and file 
dirtab = "/===" 
filetab = "|---" 

Parents={-1:"Root"} 
def add_dir(level, parent, index, k): 
    print (dirtab*level)+k 
def add_file(level, parent, index, k): 
    #Currently an empty folder gets passed to add_file; here's a quick treatment. 
    if "." in k: 
     print (filetab*level)+k 
    else: 
     print (dirtab*level)+k 
def addemup(level=0, parent=-1, index=0, di={}): 
    for k in di: 
     index +=1 
     if di[k]: 
      Parents[index]=k 
      add_dir(level, parent, index, k) 
      addemup(level+1, index, index, di[k]) 
     else: 
      add_file(level, parent, index, k) 

addemup(di=a) #dictionary from above 

这会产生，我认为会很容易修改成Tkinter的代表性的东西：

SomeRootDirectory 
/===Poems 
|---|---doyoureadme.txt 
/===Stories 
/===/===Horror 
|---|---|---rickscott.txt 
/===/===/===Trash 
|---|---|---|---notscary.txt 
/===/===Cyberpunk 
|---foo.txt 
|---bar.txt 

谢谢，这个社会是不可思议的。

Answer 1

这是一个初步的代码。通过它来告诉我你在哪里遇到问题。

Parents={-1:"Root"} 
def add_dir(level, parent, index, k): 
    print "Directory" 
    print "Level=%d, Parent=%s, Index=%d, value=%s" % (level, Parents[parent], index, k) 
def add_file(parent, index, k): 
    print "File" 
    print "Parent=%s, Index=%d, value=%s" % (Parents[parent], index, k) 
def f(level=0, parent=-1, index=0, di={}): 
    for k in di: 
     index +=1 
     if di[k]: 
      Parents[index]=k 
      add_dir(level, parent, index, k) 
      f(level+1, index, index, di[k]) 
     else: 
      add_file(parent, index, k) 

a={ 
    'SomeRootDirectory': { 
     'foo.txt': None, 
     'bar.txt': None, 
     'Stories': { 
      'Horror': { 
       'rickscott.txt' : None, 
       'Trash' : { 
        'notscary.txt' : None, 
        }, 
       }, 
      'Cyberpunk' : None 
      }, 
     'Poems' : { 
      'doyoureadme.txt' : None 
     } 
    } 
} 

f(di=a) 

Answer 2

这是一个打印所有文件名的功能。它会遍历字典中的所有键，如果它们映射的不是字典（在本例中为文件名），我们会打印出名称。否则，我们调用映射到的字典上的函数。

def print_all_files(directory): 

    for filename in directory.keys(): 
     if not isinstance(directory[filename], dict): 
      print filename 
     else: 
      print_all_files(directory[filename]) 

因此，这可以修改代码做任何你想要的，但它只是一个如何避免通过使用递归的固定深度的例子。

要理解的关键是每次print_all_files被调用时，它都不知道它在树中的深度。它只是查看那里的文件，并打印名称。如果有directores，它就会自动运行在它们上面。

Answer 3

我意识到这是一个古老的问题，但我只是寻找一个简单，干净的方式来行走嵌套的字典，这是我有限的搜索提出的最接近的东西。如果你不仅仅需要文件名，而且spicavigo的答案看起来很复杂，那么oadams的答案就不够用了。

我结束了我自己的行为，类似于os.walk如何对待导演，除了它返回所有的键/值信息。

它返回迭代和用于在嵌套http://stardict.sourceforge.net/Dictionaries.php下载的“树”的每个目录中，迭代器返回（路径，子类型的字典，值）其中：

• 路径是路径字典
• 子类型的字典是（键，字典）对每个子字典在此字典
• 值的元组的（键，值）对每个（非字典）项在此字典元组

def walk(d): 
    ''' 
    Walk a tree (nested dicts). 

    For each 'path', or dict, in the tree, returns a 3-tuple containing: 
    (path, sub-dicts, values) 

    where: 
    * path is the path to the dict 
    * sub-dicts is a tuple of (key,dict) pairs for each sub-dict in this dict 
    * values is a tuple of (key,value) pairs for each (non-dict) item in this dict 
    ''' 
    # nested dict keys 
    nested_keys = tuple(k for k in d.keys() if isinstance(d[k],dict)) 
    # key/value pairs for non-dicts 
    items = tuple((k,d[k]) for k in d.keys() if k not in nested_keys) 

    # return path, key/sub-dict pairs, and key/value pairs 
    yield ('/', [(k,d[k]) for k in nested_keys], items) 

    # recurse each subdict 
    for k in nested_keys: 
     for res in walk(d[k]): 
      # for each result, stick key in path and pass on 
      res = ('/%s' % k + res[0], res[1], res[2]) 
      yield res 

这里是我用来测试它的代码，但它有它AA夫妇其他无关（但纯）的东西：

import simplejson as json 
from collections import defaultdict 

# see https://gist.github.com/2012250 
tree = lambda: defaultdict(tree) 

def walk(d): 
    ''' 
    Walk a tree (nested dicts). 

    For each 'path', or dict, in the tree, returns a 3-tuple containing: 
    (path, sub-dicts, values) 

    where: 
    * path is the path to the dict 
    * sub-dicts is a tuple of (key,dict) pairs for each sub-dict in this dict 
    * values is a tuple of (key,value) pairs for each (non-dict) item in this dict 
    ''' 
    # nested dict keys 
    nested_keys = tuple(k for k in d.keys() if isinstance(d[k],dict)) 
    # key/value pairs for non-dicts 
    items = tuple((k,d[k]) for k in d.keys() if k not in nested_keys) 

    # return path, key/sub-dict pairs, and key/value pairs 
    yield ('/', [(k,d[k]) for k in nested_keys], items) 

    # recurse each subdict 
    for k in nested_keys: 
     for res in walk(d[k]): 
      # for each result, stick key in path and pass on 
      res = ('/%s' % k + res[0], res[1], res[2]) 
      yield res 

# use fancy tree to store arbitrary nested paths/values 
mem = tree() 

root = mem['SomeRootDirectory'] 
root['foo.txt'] = None 
root['bar.txt'] = None 
root['Stories']['Horror']['rickscott.txt'] = None 
root['Stories']['Horror']['Trash']['notscary.txt'] = None 
root['Stories']['Cyberpunk'] 
root['Poems']['doyoureadme.txt'] = None 

# convert to json string 
s = json.dumps(mem, indent=2) 

#print mem 
print s 
print 

# json.loads converts to nested dicts, need to walk them 
for (path, dicts, items) in walk(json.loads(s)): 
    # this will print every path 
    print '[%s]' % path 
    for key,val in items: 
     # this will print every key,value pair (skips empty paths) 
     print '%s = %s' % (path+key,val) 
    print 

输出看起来像：

{ 
    "SomeRootDirectory": { 
    "foo.txt": null, 
    "Stories": { 
     "Horror": { 
     "rickscott.txt": null, 
     "Trash": { 
      "notscary.txt": null 
     } 
     }, 
     "Cyberpunk": {} 
    }, 
    "Poems": { 
     "doyoureadme.txt": null 
    }, 
    "bar.txt": null 
    } 
} 

[/] 

[/SomeRootDirectory/] 
/SomeRootDirectory/foo.txt = None 
/SomeRootDirectory/bar.txt = None 

[/SomeRootDirectory/Stories/] 

[/SomeRootDirectory/Stories/Horror/] 
/SomeRootDirectory/Stories/Horror/rickscott.txt = None 

[/SomeRootDirectory/Stories/Horror/Trash/] 
/SomeRootDirectory/Stories/Horror/Trash/notscary.txt = None 

[/SomeRootDirectory/Stories/Cyberpunk/] 

[/SomeRootDirectory/Poems/] 
/SomeRootDirectory/Poems/doyoureadme.txt = None 

Answer 4

你可以使用递归步行嵌套字典

def walk_dict(dictionary): 
    for key in dictionary: 
     if isinstance(dictionary[key], dict): 
      walk_dict(dictionary[key]) 
     else: 
      #do something with dictionary[k] 
      pass 

希望帮助:)

Answer 5

a={ 
    'SomeRootDirectory': { 
     'foo.txt': None, 
     'bar.txt': None, 
     'Stories': { 
      'Horror': { 
       'rickscott.txt' : None, 
       'Trash' : { 
        'notscary.txt' : None, 
        }, 
       }, 
      'Cyberpunk' : None 
      }, 
     'Poems' : { 
      'doyoureadme.txt' : None 
     } 
    } 
} 

def dict_paths(dictionary, level=0, parents=[], paths=[]): 
    for key in dictionary: 
    parents = parents[0:level] 
    paths.append(parents + [key]) 
    if dictionary[key]: 
     parents.append(key) 
     dict_paths(dictionary[key], level+1, parents, paths) 
    return paths 

dp = dict_paths(a) 
for p in dp: 
    print '/'.join(p)