Ağaç listesinin hiyerarşiye dönüştürülmesi

Question

Attrs öğelerinin bir listesi var: parent, level, is_leaf_node, is_root_node, is_child_node.

Bu listeyi hiyerarşik dict'e dönüştürmek istiyorum. Çıktı dict Örnek:

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

ben algoritma bilmiyorum. Nasıl yapılır?

Answer 1

Burada açıklanan chmod 700 gibi daha az karmaşık, özyinelemeli bir sürümü. Tamamen tabii denenmemiş: Bu gibi basit

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

Ebeveyn olmayan her şey sizin en üst düzeyinizdir, bu yüzden bu dikteleri ilk yapın. Ardından, üst düzeydeki bir ebeveyn ile her şeyi bulmak için dizinizden ikinci bir geçiş yapın, vb ... Bir döngü veya yinelemeli işlev olarak yazılabilir. "Ebeveyn" dışında sağlanan bilgilerin hiçbirine gerçekten ihtiyacınız yok.

Answer 3

Temel olarak yapmak istediğiniz şey, topological sorting'un bir varyantıdır. Bunun en yaygın algoritması kaynak kaldırma algoritmasıdır.

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

Bu açıkça (en azından fiili Python kodu gibi) yerlerde bir çift bozuldu: yalancı kod böyle bir şey olmazdı. Ancak, umarım size algoritmanın nasıl çalışacağı hakkında bir fikir verecek olan umarım. Sahip olduğunuz öğelerde bir döngü varsa bu durumun korkunç bir şekilde başarısız olacağına dikkat edin (öğe b, ebeveyn olarak öğe öğesi b ise ana öğe olarak öğe b'yi varsayalım). Ama o zaman muhtemelen yapmak istediğiniz formatta temsil etmek imkansız olurdu.

Answer 4

Something işe yarayabilecek:

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

güzel özyinelemeli şekilde yapmak:

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