Konvertieren Baum Liste-Hierarchie dict

Habe ich eine Liste von Elementen mit attrs: übergeordnete, Ebene, is_leaf_node, is_root_node, is_child_node.

Will ich konvertieren Sie diese Liste, um die Hierarchie dict.
Beispiel der Ausgabe 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ß nicht, Algorithmus. Wie es zu tun?

  • Ist elem.Eltern ein Verweis auf ein übergeordnetes element? Oder ist es ein string? Das wird der Unterschied zwischen dem Bau dieses dict leicht oder nicht.
  • Ich habe 2 parrent attrs. Die erste ist eine "übergeordnete", die inclue-string mit parrent Namen und die zweite ist eine "parent_id" wie INT id der übergeordneten.
InformationsquelleAutor |
  1. 12

    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)
    InformationsquelleAutor Matt S.
  2. 2

    Alles ohne ein Elternteil ist Ihr top-Niveau, so stellen diese dicts ersten. Dann machen Sie einen zweiten Durchlauf durch das array, um alles zu finden mit einem Elternteil auf, dass top-level, etc... Es könnte so geschrieben werden, als eine Schleife oder eine rekursive Funktion. Sie wirklich nicht brauchen jede der zur Verfügung gestellten info neben "Eltern".

    • Im ersten Schritt habe ich dazu: In [121]: für x bei Katzen: wenn x.Eltern: falls nicht mehr aus.has_key(x.Elternteil): out - [x.parent]={} out[x.Eltern][x]={} ich habe ein Problem mit Rekursion. Wie realisieren Sie es?
    InformationsquelleAutor Trey Stout
  3. 2

    Es klingt wie das, was Sie im Grunde tun zu wollen ist eine Variante des topologische Sortierung. Der gebräuchlichste Algorithmus für diese ist die Quelle entfernen Algorithmus. Der pseudocode würde das etwa so 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])

    Dieser offensichtlich kaputt ist in ein paar Orte (zumindest als eigentlichen Python-code). Allerdings hoffentlich, dass wird Ihnen eine Idee geben, wie der Algorithmus funktioniert. Beachten Sie, dass diese scheitern wird schrecklich, wenn es einen Zyklus, in der Elemente, die Sie haben (sagen Element a Element b als Elternteil während Element b Element a als Elternteil). Aber das wäre dann wahrscheinlich unmöglich sein, Sie zu repräsentieren in dem format, das Sie wollen, sind zu tun sowieso.

    InformationsquelleAutor Jason Baker
  4. 0

    Etwas einfaches wie das gehen 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
    InformationsquelleAutor rhettg
  5. 0

    einen schönen rekursiven 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
    InformationsquelleAutor
Schreibe einen Kommentar