Как собрать иерархические данные из таблицы плоских отношений?

Question

Я пытаюсь понять, как перевести таблицу, представляющую иерархические данные обратно в код.

таблица настроена как таковой:

| id | parent_id | name | 
|----|-----------|------| 
| 1 | null | foo | 
| 2 | 1  | bar | 
| 3 | 1  | baz | 
| 4 | 3  | bif | 
| 5 | 1  | zip | 

etc... 

Такое, что, когда реконструировали, это выглядит следующим образом:

foo 
|-bar 
|-baz 
    |-bif 
|-zip 

Я изо всех сил, чтобы найти, не ужасный способ создания этого список в памяти.

В принципе, решение, к которому я пришел, просто грубо заставляет мой путь. например (в псевдо Python)

output = {} 
for item in table: 
    parent = get_parent(item) 
    if parent: 
     if parent not in output: 
      output[parent] = [] 
     output[parent_item].append(item) 

Однако, это только меня достает. Он правильно закрепляет детей под их непосредственным родителем, но только один уровень вверх. Эти данные примерно на 3 уровня глубины, поэтому, я думаю, мне придется продолжать повторять это, пока я не смогу найти больше объектов с родителями.

Достаточно сказать, что мое решение плохое, хрупкое, и я не знаю, что еще делать. Каков правильный способ решить эту проблему?

Answer 1

Проверьте это быстрое решение.

мы можем построить словарь, чтобы мы могли отображать ключи с именами.

D={"1":"foo","2":"bar","3":"baz","4":"bif","5":"zip","Non":'Root'} 
get_parent_id=["Non","1","1","3","1"] 
get_name=["foo","bar","baz","bif","zip"] 

result = {} 
for k,v in zip(get_parent_id,get_name): 
    result.setdefault(D[k], {}).update({v:{}}) 

мы строим словарь, от parent ids и имен.

{'baz': {'bif': {}}, 'foo': {'baz': {}, 'bar': {}, 'zip': {}}, 'Root': {'foo': {}}} 

Теперь мы должны работать над другими значениями. мы можем использовать логический словарь {key:boolean value}, чтобы отметить, что является корнем здесь, всякий раз, когда мы находим значение, которое является ключом, мы отмечаем его как false, поскольку он не может быть корневым.

формально, Root - это ключи, которые не отображаются в значениях всех ключей.

boolRoot= len(result)*[True] 
bDict=dict(zip(result.keys(),boolRoot)) 

# {'Root': True, 'foo': True, 'baz': True} 

Затем мы пересекаем значение, и мы заменим значение внутри с помощью ключа и значения, что карт для детей

for k,v in result.iteritems(): 
    for item in v.keys(): 
     #print item,result[k][item] 
     if item in result.keys(): 
      bDict[item]=False 
      result[k][item]=result[item] 

print result 
print bDict 

В конце концов, мы имеем:

{'baz': {'bif': {}}, 'foo': {'baz': {'bif': {}}, 'bar': {}, 'zip': {}}, 'Root': {'foo': {'baz': {'bif': {}}, 'bar': {}, 'zip': {}}}} #result 
{'Root': True, 'foo': False, 'baz': False} #bDict 

Корень, это ключ со значением True на основе вышеупомянутого предположения. Вам нужно только получить result[name], где bDict[name] is True

Надеюсь, что это поможет вам придумать лучшее решение.