从具有级别的列表构造树 [英] Construct a tree from a list with levels

问题描述

我有一些数据（Python 列表的 dict s）看起来像：

I have some data(Python list of dicts) which looks like:

[
    {'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},
    ...
]

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

It represents a tree, which looks like:

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

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

And here's what I want: Efficient, elegant(Pythonic?) way to construct a tree from the array which has levels(in other words, depths) only.

这样我就可以访问tree：

So that I could access to the tree:

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) # => []

我一直在努力实现一些递归功能，但突然间我的大脑停止了工作。我正在等待您的帮助。

I struggled to make some recursive functions to achieve it, but suddenly my brain stopped working. I'm waiting for your help.

谢谢。

---编辑---

这就是我写的内容：

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>

推荐答案

代码应该很简单。您的计划意味着孩子要下订单，因此我将使用列表。

The code should be simple. Your scheme implies there is an order to the children, so I will use a 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 的新节点。返回根目录并重复执行，而您还没有完成对数据的迭代。

The algorithm is also simple. Start at the root. Iterate over the data. While you are less than "level" nodes deep, continue moving down the children going to the last child appended attempting to go down the last node in children. If attempting to index into the last child fails, then we know we are where we have to be (assuming the input is well behaved!) and we append a new node with the value "value". If you don't fail and make it to "level", append a new node with the value "value". Return to the root and repeat while you are not done iterating over the data.

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>

这篇关于从具有级别的列表构造树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！