Konvertieren von Baumliste Hierarchie dict
-
09-09-2019 - |
Frage
Ich habe eine Liste von Elementen mit attrs: Eltern, Ebene, is_leaf_node, is_root_node, is_child_node
.Ich möchte diese Liste Hierarchie dict konvertieren. Ausgabebeispiel 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 geht?
Lösung
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)
Andere Tipps
Alles ohne einen Elternteil ist Ihr Top-Level, so zuerst jene dicts machen. Dann einen zweiten Durchlauf durch das Array zu tun an diesem Top-Level-alles mit einem Elternteil zu finden, etc ... Es könnte als eine Schleife oder eine rekursive Funktion geschrieben werden. Sie wirklich nicht jede der bereitgestellten Informationen benötigen neben „Eltern“.
Es klingt wie, was Sie im Grunde ist eine Variante des topologischen tun wollen Sortierung . Der häufigste Algorithmus hierfür ist die Quelle Entfernung Algorithmus. Der Pseudo-Code würde wie folgt 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])
Dies ist offensichtlich in ein paar Stellen gebrochen (zumindest als tatsächlicher Python-Code). Allerdings hoffentlich , die Ihnen eine Vorstellung davon, wie der Algorithmus funktioniert. Beachten Sie, dass dies schrecklich scheitern wird, wenn es in den Einzelteilen ein Zyklus ist man (sagen Punkt a b als Elternteil hat Punkt während Punkt b Punkt a als Elternteil hat) haben. Aber dann wäre das wohl unmöglich sein, in dem Format repräsentieren Sie wollen auf jeden Fall tun.
etwas Einfaches wie dies funktionieren 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
eine schöne rekursive 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