从 [parentid， name] 目录字典到完整路径字典

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 MasterFileTable(我正在阅读(中经常是这样的。

这个想法可能是：">到达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'}