트리 목록을 계층 구조로 변환합니다

Question

부모, 레벨, is_leaf_node, is_root_node, is_child_node : attrs가있는 요소 목록이 있습니다.

이 목록을 계층 구조 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

부모가없는 모든 것이 당신의 최상위 레벨이므로 먼저 그 icts를 만드십시오. 그런 다음 배열을 통해 두 번째 패스를 수행하여 해당 상단 레벨의 부모와 함께 모든 것을 찾으십시오 ... 루프 또는 재귀 기능으로 작성 될 수 있습니다. 당신은 실제로 "부모"외에 제공된 정보가 필요하지 않습니다.

Answer 3

기본적으로하고 싶은 것은 변형입니다. 토폴로지 분류. 이를위한 가장 일반적인 알고리즘은 소스 제거 알고리즘입니다. 유사 코드는 다음과 같이 보입니다.

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를 가지고 있으며 항목 B는 부모로서 항목 A를 가지고 있음). 그러나 어쨌든 원하는 형식으로 표현하는 것은 불가능할 것입니다.

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