تحويل قائمة الأشجار إلى DICT التسلسل الهرمي

Question

لدي قائمة بالعناصر مع الأرجاجات: الوالد، المستوى، 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':{}
            },}

أنا لا أعرف الخوارزمية. كيف افعلها؟

Answer 1

إليك نسخة تقليدية أقل تطورا مثل 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)

Answer 2

كل شيء بدون أحد الوالدين هو مستواك العلوي، لذلك اجعل تلك المؤقتات أولا. ثم قم بالمرور الثاني من خلال صفيفك للعثور على كل شيء مع أحد الوالدين في هذا المستوى الأعلى، إلخ ... يمكن كتابته كحلقة أو وظيفة متكررة. أنت حقا لا تحتاج إلى أي من المعلومات المقدمة إلى جانب "الوالد".

Answer 3

يبدو وكأنه ما تريد في الأساس القيام به هو متغير الفرز الطوبولوجي. وبعد الخوارزمية الأكثر شيوعا لهذا هي خوارزمية إزالة المصدر. ستبدو 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 على عنصر كوالد). ولكن بعد ذلك من شأنه أن يكون من المستحيل التمثيل في الشكل الذي تريد القيام به على أي حال.

Answer 4

شيء بسيط مثل هذا قد يعمل:

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

طريقة متكررة لطيفة للقيام بذلك:

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