从[parentid，name]目录dict到完整路径di

Question

我的目录目录是[parentid, name]，如下所示：

D = {0: [-1, 'C:'],
     1: [0, 'BLAH'], 
     2: [0, 'TEMP'], 
     3: [1, 'BOOO'], 
     4: [1, 'AZAZ'], 
     5: [2, 'ABCD']}

我想从这条路走到完整的路：

FULLPATHS = {}
for key, path in D.iteritems():
    newpath = path[1]
    if path[0] != -1:
         newpath = FULLPATHS[path[0]] + '\\' + newpath
    FULLPATHS[key] = newpath

它的工作原理是：

 {0: 'C:', 1: 'C:\\BLAH', 2: 'C:\\TEMP', 3: 'C:\\BLAH\\BOOO', 4: 'C:\\BLAH\\AZAZ', 5: 'C:\\TEMP\\ABCD'}

但现在，如果密钥是非递增的目录ID，则会出现棘手的部分：

 D = {0: [-1, 'C:'],
     7: [0, 'TEMP'], 
     3: [122, 'BOOO'], 
     4: [122, 'AZAZ'], 
     5: [7, 'ABCD'],
     122: [0, 'BLAH']}

在NTFS主文件表中经常是这样的（我正在阅读）

这个想法可能是：“当到达3: [122, 'BOOO']时，让我们等待并推迟这个，一旦dir#122稍后将被处理”。但这需要许多连续的循环来确保所有操作都是正确的

如何从[parentid, name]目录方案转到完整路径？

注意：这个问题不是Python特有的，所以我不是在寻找os.path解决方案，而是一个一般性的问题

Answer 1

一种可能性：对于每一个元素，都要沿着链子往上走，直到你找到根为止

FULLPATHS=dict()
for k in D:
    parent = D[k][0]
    chain = [ D[k][1] ]
    while parent != -1: # here I assume root's parent is always -1
        chain.append(D[parent][1])
        parent = D[parent][0]
    FULLPATHS[k] = '\\'.join(reversed(chain))

甚至，利用已经建立的前缀路径：

FULLPATHS = { 0: 'C:' }
for k in D:
    i = k
    chain = []
    while i not in FULLPATHS:
        chain.append(D[i][1])
            i = D[i][0]
    FULLPATHS[k] = '\\'.join([FULLPATHS[i]] + list(reversed(chain)))

print(FULLPATHS)

Answer 2

我正在尝试这样的解决方案：如果一个家长还没有被“完整路径教育”，那就先做一次，一劳永逸

FULLPATHS = {0: 'C:'}

def do(id):
    parentid = D[id][0]
    name = D[id][1]
    if id not in FULLPATHS:
        if parentid not in FULLPATHS:
            do(parentid)
        FULLPATHS[id] = FULLPATHS[parentid] + '\\' + name

for k, v in D.iteritems():
    do(k)

print FULLPATHS  

#{0: 'C:', 3: 'C:\\BLAH\\BOOO', 4: 'C:\\BLAH\\AZAZ', 5: 'C:\\TEMP\\ABCD', 7: 'C:\\TEMP', 122: 'C:\\BLAH'}