将树列表转换为层次结构di

Question

我有一个属性为的元素列表：parent，level，is_leaf_node，is_root_node，is_child_node。

我要将此列表转换为层次结构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

没有父母的一切都是你的最高境界，所以先做这些决定。然后对数组进行第二次遍历，以查找父级位于顶层的所有内容，等等。。。它可以写成循环或递归函数。你真的不需要任何提供的信息除了“家长”。

Answer 2

听起来你基本上想做的是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作为父项），则此操作将失败得可怕。但那可能就不可能用你想要的格式来表示了。

Answer 3

下面是一个不太复杂的递归版本，如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)