Konwertowanie listy drzew do hierarchii Dict

Question

Mam listę elementów z attrs: rodzic, poziom, is_leaf_node, is_root_node, is_child_node.

Chcę przekonwertować tę listę do dyktatury hierarchii. Przykład wyjściowego dict:

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

nie wiem algorytmu. Jak to zrobić?

Answer 1

Oto mniej wyrafinowana, rekurencyjna wersja, taka jak chmod 700 opisana. Całkowicie niesprawdzone przedmiotu:

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

Wszystko bez rodzica jest najwyższym poziomem, więc najpierw wykonaj te dyktatury. Następnie wykonaj drugie przejście przez tablicę, aby znaleźć wszystko z rodzica na tym najwyższym poziomie, itd ... Może to być napisane jako pętla lub funkcja rekursywna. Naprawdę nie potrzebujesz żadnej z podanych informacji oprócz "rodzica".

Answer 3

Wygląda na to, że zasadniczo chcesz zrobić to wariant topological sorting. Najpopularniejszym algorytmem jest algorytm usuwania źródła. Pseudokod wyglądałby mniej więcej tak:

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

To oczywiście jest uszkodzony w kilku miejscach (przynajmniej jako rzeczywistego kodu Pythona). Jednakże, mam nadzieję, że, który da ci pojęcie o tym, jak działa algorytm. Zauważ, że to się nie powiedzie, jeśli istnieje cykl w przedmiotach, które posiadasz (np. Pozycja ma element b jako element nadrzędny, a element b ma element a jako element nadrzędny). Ale wtedy to byłoby niemożliwe do przedstawienia w formacie, który i tak chcesz zrobić.

Answer 4

coś prostego, jak to może działać:

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

miłym rekurencyjny sposób to zrobić:

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