Convertendo lista de árvore para dict hierarquia

Question

Eu tenho uma lista de elementos com attrs:. Pais, nível, is_leaf_node, is_root_node, is_child_node

Eu quero converter essa lista para dict hierarquia. Exemplo de Dict saída:

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

Eu não sei algoritmo. Como fazer isso?

Answer 1

Aqui está uma versão menos sofisticada, recursivo como chmod 700 descrito. Completamente testado é claro:

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

Tudo sem um pai é o seu nível mais alto, então fazer essas dicts primeiro. Em seguida, fazer uma segunda passagem através de sua matriz para encontrar tudo com um dos pais nesse nível superior, etc ... Pode ser escrito como um loop ou uma função recursiva. Você realmente não precisa de nenhum das informações fornecidas, além de "pai".

Answer 3

Parece que você está querendo basicamente a fazer é uma variante do topológica classificação . O algoritmo mais comum para isso é o algoritmo de remoção fonte. O pseudocódigo seria algo parecido com isto:

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

Isto, obviamente, é quebrado em um par de lugares (pelo menos como código Python real). No entanto, espero , que lhe dará uma idéia de como o algoritmo funciona. Note que este irá falhar terrivelmente se há um ciclo nos itens que você tem (digamos um item tem alínea b como um pai quando o item b tem um item como um pai). Mas, então, que provavelmente seria impossível representar no formato que você está querendo fazer de qualquer maneira.

Answer 4

Algo simples como este trabalho poder:

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

uma forma recursiva bom para fazê-lo:

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