从一个列表中构建一棵具有层级的树形结构。

Question

从一个列表中构建一棵具有层级的树形结构。

3

我有一些数据（Python list 中的 dict），看起来像这样：

[
    {'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>

- hallazzang

你到目前为止尝试了什么？展示一下你的工作。SO并不是来为你编写代码的。 - Soviut

@Soviut，我写了一些测试代码，但是它们没有起作用，而且非常丑陋。我应该发布这些代码吗？ - hallazzang

是的，请发布您的尝试，以便我们可以帮助您纠正问题。 - Soviut

@Soviut，我已经发布了。 - hallazzang

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- juanpa.arrivillaga · Accepted Answer

代码应该要简单易懂。你的方案涉及到子元素的顺序，所以我会使用一个 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>