将树列表转换为层次结构字典

Question

我有一个带有属性的元素列表：parent、level、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':{}
            },}

我不知道算法。 怎么做？

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

听起来您基本上想做的是拓扑排序的变体。 最常见的算法是源删除算法。 伪代码看起来像这样：

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 作为父项），则这将严重失败。 但无论如何，这可能无法以您想要的格式表示。

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