Tree-Liste in Hierarchie-Dict konvertieren

Question

Ich habe eine Liste von Elementen mit Attrs: Parent, Ebene, is_leaf_node, is_root_node, is_child_node.

Ich möchte diese Liste in die Hierarchie dict konvertieren. Ausgabebeispiel dict:

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

Ich weiß Algorithmus nicht. Wie es geht?

Answer 1

Hier ist eine weniger anspruchsvolle, rekursive Version wie chmod 700 beschrieben. Völlig ungetestet natürlich:

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

Alles ohne einen Elternteil ist Ihr Top-Level, also machen Sie diese Dicts zuerst. Dann machen Sie einen zweiten Durchlauf durch Ihr Array, um alles mit einem Elternteil auf dieser obersten Ebene usw. zu finden ... Es könnte als eine Schleife oder eine rekursive Funktion geschrieben werden. Sie brauchen wirklich keine der bereitgestellten Informationen neben "Eltern".

Answer 3

Es klingt wie das, was Sie im Grunde wollen, ist eine Variante von topological sorting. Der häufigste Algorithmus hierfür ist der Quellenentfernungsalgorithmus. Der Pseudo-Code würde wie folgt aussehen:

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]) 

Dies ist offensichtlich in ein paar Stellen gebrochen wird (zumindest als eigentlicher Python-Code). Allerdings wird hoffentlich, die Ihnen eine Vorstellung davon geben, wie der Algorithmus funktionieren wird. Beachten Sie, dass dies fürchterlich scheitern wird, wenn es einen Zyklus in den Elementen gibt, die Sie haben (sagen wir, dass Element a Element b als ein Elternelement hat, während Objekt b Element a als Elternelement hat). Aber dann wäre es wahrscheinlich unmöglich, das Format darzustellen, das Sie sowieso wollen.

Answer 4

etwas Einfaches wie dies funktionieren könnte:

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

eine schöne rekursive Art und Weise, es zu tun:

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