تحويل قائمة الأشجار إلى DICT التسلسل الهرمي
-
09-09-2019 - |
سؤال
لدي قائمة بالعناصر مع الأرجاجات: الوالد، المستوى، is_leaf_node، is_root_node، is_child_node.
أريد تحويل هذه القائمة إلى DICT التسلسل الهرمي. مثال على إخراج Dict:
{
'Technology':
{
'Gadgets':{},
'Gaming':{},
'Programming':
{
'Python':{},
'PHP':{},
'Ruby':{},
'C++':{}
},
'Enterprise':{},
'Mac':{},
'Mobile':{},
'Seo':{},
'Ui':{},
'Virtual Worlds':{},
'Windows':{},
},
'News':{
'Blogging':{},
'Economics':{},
'Journalism':{},
'Politics':{},
'News':{}
},}
أنا لا أعرف الخوارزمية. كيف افعلها؟
المحلول
إليك نسخة تقليدية أقل تطورا مثل Chmod 700 الموصوفة. غير مختبر تماما بالطبع:
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)
نصائح أخرى
كل شيء بدون أحد الوالدين هو مستواك العلوي، لذلك اجعل تلك المؤقتات أولا. ثم قم بالمرور الثاني من خلال صفيفك للعثور على كل شيء مع أحد الوالدين في هذا المستوى الأعلى، إلخ ... يمكن كتابته كحلقة أو وظيفة متكررة. أنت حقا لا تحتاج إلى أي من المعلومات المقدمة إلى جانب "الوالد".
يبدو وكأنه ما تريد في الأساس القيام به هو متغير الفرز الطوبولوجي. وبعد الخوارزمية الأكثر شيوعا لهذا هي خوارزمية إزالة المصدر. ستبدو Pseudoodocode شيء مثل هذا:
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])
من الواضح أن هذا مكسور في بضع أماكن (على الأقل ككود بيثون الفعلي). ومع ذلك، نأمل هذا سوف يمنحك فكرة عن كيفية عمل الخوارزمية. لاحظ أن هذا ستفشل بشكل فظيع إذا كانت هناك دورة في العناصر التي لديك (قل العنصر A يحتوي على عنصر B كوالد بينما يحتوي العنصر B على عنصر كوالد). ولكن بعد ذلك من شأنه أن يكون من المستحيل التمثيل في الشكل الذي تريد القيام به على أي حال.
شيء بسيط مثل هذا قد يعمل:
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
طريقة متكررة لطيفة للقيام بذلك:
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