从具有级别的列表构造一棵树

我有一些数据（Pythonlist of dicts) 看起来像：

[
    {'value': 'A', 'level': 0},
    {'value': 'B', 'level': 1},
    {'value': 'C', 'level': 2},
    {'value': 'D', 'level': 1},
    {'value': 'E', 'level': 2},
    {'value': 'F', 'level': 2},
    {'value': 'G', 'level': 0},
    {'value': 'H', 'level': 1},
    ...
]

它代表一棵树，看起来像：

<root>
|
+---A
|   |
|   +---B
|   |   |
|   |   +---C
|   |
|   +---D
|       |
|       +---E
|       |
|       +---F
+---G
    |
    +---H

这是我想要的是：高效、优雅（Pythonic？）的方法从仅具有级别（换句话说，深度）的数组构造树。

这样我就可以访问树：

root = build_tree(data) # or somewhat proper arguments

print(root.children) # => [<Node A>, <Node G>]
print(root.children[0].children) # => [<Node B>, <Node D>]
print(root.children[0].children[1].children]) # => [<Node E>, <Node F>]
print(root.children[1].children) # => [Node G]
print(root.children[1].children[0].children) # => []

我努力编写一些递归函数来实现它，但突然我的大脑停止了工作。我正在等待你的帮助。

谢谢。

--- 已编辑 ---

这是我写的：

class TreeNode(object):
    def __init__(self, parent, value):
        self.parent = parent
        self.children = []

        self.__dict__.update(**value)

    def __repr__(self):
        return '<TreeNode %s>' % self.value

def build_tree(list, parent, start_idx=0, depth=0):
    current = TreeNode(parent, list[start_idx])
    parent.children.append(current)

    for idx in xrange(start_idx + 1, len(list)):
        if list[idx]['level'] == current.level:
            build_tree(list, parent, idx)
        elif list[idx]['level'] == current.level + 1:
            build_tree(list, current, idx)
        elif list[idx]['level'] < current.level:
            break

def print_tree(root, depth=0):
    for child in root.children:
        print('  ' * depth + '%r' % child)
        print_tree(child, depth + 1)

if __name__ == '__main__':
    data = [
        {'value': 'A', 'level': 0},
        {'value': 'B', 'level': 1},
        {'value': 'C', 'level': 2},
        {'value': 'D', 'level': 1},
        {'value': 'E', 'level': 2},
        {'value': 'F', 'level': 2},
        {'value': 'G', 'level': 0},
        {'value': 'H', 'level': 1},
    ]

    root = TreeNode(None, {'value': 'root'})
    build_tree(data, root)

    print_tree(root)

它给出：

<TreeNode A>
  <TreeNode B>
    <TreeNode C>
    <TreeNode E>
    <TreeNode F>
    <TreeNode F>
  <TreeNode D>
    <TreeNode E>
    <TreeNode F>
    <TreeNode F>
  <TreeNode D>
    <TreeNode E>
    <TreeNode F>
    <TreeNode F>
  <TreeNode H>
<TreeNode G>
  <TreeNode H>

代码应该很简单。你的方案意味着对孩子们有一个命令，所以我将使用list.

In [8]: class Node:
   ...:     def __init__(self, val=None):
   ...:         self.value = val
   ...:         self.children = []
   ...:     def __repr__(self):
   ...:         return "<Node {}>".format(self.value)
   ...:

算法也很简单。从根开始。迭代数据。虽然你小于"level"节点深，继续向下移动孩子们去附加最后一个子项尝试深入子节点的最后一个节点。如果尝试索引最后一个子节点失败，那么我们知道我们已经到达了我们必须到达的位置（假设输入表现良好！），并且我们附加一个带有值的新节点"value"。如果你没有失败并成功"level"，附加一个带有值的新节点"value"。在未完成数据迭代时返回根并重复。

In [9]: root = Node()

In [10]: for record in data:
    ...:     last = root
    ...:     for _ in range(record['level']):
    ...:         last = last.children[-1]
    ...:     last.children.append(Node(record['value']))
    ...:

现在，检查我们的树：

In [12]: root.children
Out[12]: [<Node A>, <Node G>]

In [13]: root.children[0].children
Out[13]: [<Node B>, <Node D>]

In [14]: root.children[0].children[1].children
Out[14]: [<Node E>, <Node F>]

In [15]: root.children[1].children
Out[15]: [<Node H>]

In [16]: root.children[1].children[0].children
Out[16]: []

运用你的得心应手print_tree功能：

In [24]: def print_tree(root, depth=0):
    ...:     for child in root.children:
    ...:         print('  ' * depth + '%r' % child)
    ...:         print_tree(child, depth + 1)
    ...:

In [25]: print_tree(root)
<Node A>
  <Node B>
    <Node C>
  <Node D>
    <Node E>
    <Node F>
<Node G>
  <Node H>