漫步/遍歷任意深度的嵌套字典（字典表示一個目錄樹）

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)