Chuyển đổi danh sách cây thành cấu trúc phân cấp

Question

Tôi có một danh sách các phần tử có attrs: parent, level, is_leaf_node, is_root_node, is_child_node.

Tôi muốn chuyển đổi danh sách này sang định dạng phân cấp. Ví dụ về đầu ra dict:

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

Tôi không biết thuật toán. Làm thế nào để làm nó?

Answer 1

Dưới đây là phiên bản đệ quy, phức tạp hơn như chmod 700 được mô tả. Hoàn toàn chưa được kiểm tra tất nhiên:

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

Mọi thứ không có cha mẹ là cấp cao nhất của bạn, vì vậy hãy đặt những dấu gạch đó trước tiên. Sau đó thực hiện lần thứ hai thông qua mảng của bạn để tìm mọi thứ với cha mẹ ở cấp cao nhất đó, v.v ... Nó có thể được viết dưới dạng vòng lặp hoặc hàm đệ quy. Bạn thực sự không cần bất kỳ thông tin nào được cung cấp bên cạnh "cha mẹ".

Answer 3

Nghe có vẻ như những gì bạn về cơ bản muốn làm là một biến thể của topological sorting. Thuật toán phổ biến nhất cho điều này là thuật toán loại bỏ nguồn. Mã giả sẽ trông giống như sau:

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

Điều này rõ ràng bị hỏng ở một vài nơi (ít nhất là mã Python thực). Tuy nhiên, hy vọng sẽ cung cấp cho bạn ý tưởng về cách thuật toán hoạt động. Lưu ý rằng điều này sẽ thất bại khủng khiếp nếu có một chu kỳ trong các mục bạn có (nói mục a có mục b làm cha mẹ trong khi mục b có mục là phụ huynh). Nhưng sau đó có lẽ sẽ không thể đại diện cho định dạng bạn muốn làm.

Answer 4

Something đơn giản như thế này có thể làm việc:

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

một cách đệ quy tốt đẹp để làm điều đó:

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