从具有级别的列表构造树

一尘不染

从具有级别的列表构造树

algorithm

我有一些数据（Python中list的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>

阅读 232

2020-07-28

共1个答案

一尘不染

代码应该很简单。您的计划暗示孩子们有命令，所以我将使用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
"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>

2020-07-28