轉換樹列表層次結構字典

我有一個元素列表與attrs：父級，級別，is_leaf_node，is_root_node，is_child_node。轉換樹列表層次結構字典

我想將此列表轉換爲層次結構字典。示例輸出字典：

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

我不知道算法。怎麼做？

來源

2009-04-16 Alexandr

是elem.parent到父元素的引用？或者它是一個字符串？這將是輕鬆構建這個詞典的區別。 – 2009-04-16 18:41:10

我有2個parrent attrs。首先是一個「父」，其中包含帶有父類名稱的字符串，其次是包含父類的INT id的「parent_id」。 – Alexandr 2009-04-17 14:33:59

下面是一個不太複雜的遞歸版本，如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)

來源

2009-04-16 19:02:37

沒有父母的一切都是你的最高水平，所以先讓這些詞典。然後再通過你的數組進行第二次遍歷，以找到在頂層有父級的所有東西，等等......它可以寫成循環或遞歸函數。除了「父母」之外，你真的不需要任何提供的信息。

來源

2009-04-16 18:13:53

這聽起來像你基本上想要做的是topological sorting的變種。最常見的算法是源去除算法。僞代碼會是這個樣子：

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

這顯然是在幾個地方壞了（至少是實際的Python代碼）。但是，希望，這將給你一個算法如何工作的想法。請注意，如果您的項目中存在週期（例如，項目a將項目b作爲父項目，而項目b將項目a作爲父項目），則這會失敗。但是，這可能無法用您想要的格式來表示。

來源

2009-04-16 18:42:00

一些簡單的像這可能工作：

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

來源

2009-04-17 01:05:37 rhettg

一個不錯的遞歸的方式做到這一點：

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

來源

2017-05-04 12:33:11 style

轉換樹列表層次結構字典

回答

相關問題