La conversión de lista de árbol de jerarquía dict

Question

Tengo una lista de elementos con attrs: los padres, nivel, is_leaf_node, is_root_node, is_child_node

.

Quiero convertir esta lista para dict jerarquía. Ejemplo de dict salida:

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

No sé algoritmo. ¿Cómo hacerlo?

Answer 1

Esta es una versión menos sofisticada, recursiva como se describe chmod 700. No está comprobado por supuesto:

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

Todo sin un padre es su nivel superior, así que esos predice primero. A continuación, hacer una segunda pasada a través de la matriz de encontrar todo con un padre en ese nivel superior, etc ... Se podría escribir como un bucle o una función recursiva. Usted realmente no necesita cualquiera de la información proporcionada, además de "padre".

Answer 3

Parece que lo que está básicamente querer hacer es una variante de topológica de clasificación . El algoritmo más común de esto es el algoritmo de eliminación de la fuente. El pseudocódigo sería algo como esto:

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

Esto, obviamente, se rompe en un par de lugares (por lo menos tan código Python real). Sin embargo, es de esperar que le dará una idea de cómo funciona el algoritmo. Tenga en cuenta que esto se producirá un error horrible si hay un ciclo en los elementos que tiene (decir el punto a punto b tiene como uno de sus padres, mientras que el punto b tiene un elemento como un padre). Pero entonces que probablemente sería imposible de representar en el formato que está queriendo hacer de todos modos.

Answer 4

Algo tan simple como esto podría funcionar:

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

una forma recursiva agradable hacerlo:

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