Conversione dell'albero gerarchico in dict

Question

Ho una lista di elementi con attrs: genitore, livello, is_leaf_node, is_root_node, is_child_node.

Voglio convertire questa lista in gerarchia dict. Esempio di dict uscita:

{ 
     'Technology': 
      { 
      'Gadgets':{}, 
      'Gaming':{}, 
      'Programming': 
       { 
        'Python':{}, 
        'PHP':{}, 
        'Ruby':{}, 
        'C++':{} 
       }, 
      'Enterprise':{}, 
      'Mac':{}, 
      'Mobile':{}, 
      'Seo':{}, 
      'Ui':{}, 
      'Virtual Worlds':{}, 
      'Windows':{}, 
      }, 
     'News':{ 
      'Blogging':{}, 
      'Economics':{}, 
      'Journalism':{}, 
      'Politics':{}, 
      'News':{} 
      },} 

Non lo so algoritmo. Come farlo?

Answer 1

Ecco una versione meno sofisticata e ricorsiva come chmod 700 descritta. Completamente testati ovviamente:

def build_tree(nodes): 
    # create empty tree to fill 
    tree = {} 

    # fill in tree starting with roots (those with no parent) 
    build_tree_recursive(tree, None, nodes) 

    return tree 

def build_tree_recursive(tree, parent, nodes): 
    # find children 
    children = [n for n in nodes if n.parent == parent] 

    # build a subtree for each child 
    for child in children: 
     # start new subtree 
     tree[child.name] = {} 

     # call recursively to build a subtree for current node 
     build_tree_recursive(tree[child.name], child, nodes) 

Answer 2

Tutto senza un genitore è il tuo livello più alto, quindi rendi questi termini prima. Quindi fai un secondo passaggio attraverso l'array per trovare tutto con un genitore a quel livello superiore, ecc ... Potrebbe essere scritto come un loop o una funzione ricorsiva. Non hai davvero bisogno di nessuna delle informazioni fornite oltre a "genitore".

Answer 3

Sembra che quello che fondamentalmente si vuole fare è una variante di topological sorting. L'algoritmo più comune per questo è l'algoritmo di rimozione della fonte. Il pseudocodice sarebbe simile a questa:

import copy 
def TopSort(elems): #elems is an unsorted list of elements. 
    unsorted = set(elems) 
    output_dict = {} 
    for item in elems: 
     if item.is_root(): 
      output_dict[item.name] = {} 
      unsorted.remove(item) 
      FindChildren(unsorted, item.name, output_dict[item.name]) 
    return output_dict 

def FindChildren(unsorted, name, curr_dict): 
    for item in unsorted: 
     if item.parent == name: 
      curr_dict[item.name] = {} 
      #NOTE: the next line won't work in Python. You 
      #can't modify a set while iterating over it. 
      unsorted.remove(item) 
      FindChildren(unsorted, item.name, curr_dict[item.name]) 

Questo, ovviamente, è suddiviso in un paio di posti (almeno per quanto codice Python reale). Tuttavia, si spera che sia che ti darà un'idea di come funzionerà l'algoritmo. Nota che questo fallirà orribilmente se c'è un ciclo negli elementi che hai (ad esempio l'articolo a ha l'elemento b come genitore mentre l'articolo b ha l'articolo a come genitore). Ma probabilmente sarebbe impossibile rappresentarlo nel formato che vorresti comunque fare.

Answer 4

Qualcosa di semplice come questo potrebbe funzionare:

def build_tree(category_data): 
    top_level_map = {} 
    cat_map = {} 
    for cat_name, parent, depth in cat_data: 
    cat_map.setdefault(parent, {}) 
    cat_map.setdefault(cat_name, {}) 
    cat_map[parent][cat_name] = cat_map[cat_name] 
    if depth == 0: 
     top_level_map[cat_name] = cat_map[cat_name] 

    return top_level_map 

Answer 5

un modo ricorsivo bello farlo:

def build_tree(elems): 
    elem_with_children = {} 

    def _build_children_sub_tree(parent): 
     cur_dict = { 
      'id': parent, 
      # put whatever attributes here 
     } 
     if parent in elem_with_children.keys(): 
      cur_dict["children"] = [_build_children_sub_tree(cid) for cid in elem_with_children[parent]] 
     return cur_dict 

    for item in elems: 
     cid = item['id'] 
     pid = item['parent'] 
     elem_with_children.setdefault(pid, []).append(cid) 

    res = _build_children_sub_tree(-1) # -1 is your root 
    return res