从具有级别的列表构建一棵树 [英] Construct a tree from a list with levels
问题描述
我有一些数据(Python list of dicts)，看起来像:
它代表一棵树，看起来像:
|+---A|||+---B|||||+---C|||+---D|||+---E|||+---F+---G|+---H 这里是我想要的:高效、优雅(Pythonic?)的方法来从只有级别(换句话说，深度)的数组构造树.
这样我就可以访问这棵树了:
root = build_tree(data) # 或一些适当的参数打印(root.children)# =>[<节点A>，<节点G>]打印(root.children[0].children)# =>[<节点B>，<节点D>]打印(root.children[0].children[1].children])#=>[<节点E>，<节点F>]打印(root.children[1].children)# =>[节点G]打印(root.children[1].children[0].children)#=>[]我努力做一些递归函数来实现它，但突然我的大脑停止工作.我在等待你的帮助.
谢谢.
--- 编辑---
这是我写的:
class TreeNode(object):def __init__(self, parent, value):self.parent = 父母self.children = []self.__dict__.update(**值)def __repr__(self):返回<树节点 %s>"% 自我价值def build_tree(list, parent, start_idx=0, depth=0):当前 = TreeNode(parent, list[start_idx])parent.children.append(当前)对于 xrange(start_idx + 1, len(list)) 中的 idx:如果 list[idx]['level'] == current.level:build_tree(列表，父级，idx)elif list[idx]['level'] == current.level + 1:build_tree(列表，当前，idx)elif 列表[idx]['level'] <当前水平:休息def print_tree(根，深度= 0):对于 root.children 中的孩子:打印('' * 深度 + '%r' % 子级)打印树(孩子，深度+ 1)如果 __name__ == '__main__':数据 = [{'值':'A'，'级别':0}，{'值':'B'，'级别':1}，{'值':'C'，'级别':2}，{'值':'D'，'级别':1}，{'值':'E'，'级别':2}，{'值':'F'，'级别':2}，{'值':'G'，'级别':0}，{'值':'H'，'级别':1}，]root = TreeNode(None, {'value': 'root'})build_tree(数据，根)打印树(根)它给出:
<树节点B><树节点 C><树节点E><树节点F><树节点F><树节点 D><树节点E><树节点F><树节点F><树节点 D><树节点E><树节点F><树节点F><树节点H><树节点G><树节点H> 代码应该简单.你的方案暗示孩子们有一个命令，所以我将使用一个list.
在[8]中:类节点:...: def __init__(self, val=None):...: self.value = val...:self.children = []...: def __repr__(self):...: 返回 "".format(self.value)...: 算法也很简单.从根开始.迭代数据.当您的节点深度小于 "level" 节点时，继续向下移动子节点到 最后一个附加的子节点，尝试向下移动子节点中的最后一个节点.如果尝试对最后一个子节点进行索引失败，那么我们知道我们到达了我们必须到达的位置(假设输入表现良好！)并且我们附加一个值为 "value" 的新节点.如果您没有失败并使其达到 "level"，则附加一个值为 "value" 的新节点.返回到根并在您没有完成对数据的迭代时重复.
在[9]中:root = Node()In [10]:用于记录数据:...:最后一个 = 根...:对于范围内的_(记录['级别']):...: last = last.children[-1]...: last.children.append(Node(record['value']))...:现在，查看我们的树:
在[12]中:root.children输出[12]:[<节点A>，<节点G>]在 [13] 中:root.children[0].children输出[13]:[<节点B>，<节点D>]在 [14] 中:root.children[0].children[1].children输出[14]:[<节点E>，<节点F>]在 [15] 中:root.children[1].children输出[15]:[<节点H>]在 [16] 中:root.children[1].children[0].children出[16]:[]使用您方便的print_tree 函数:
在 [24]: def print_tree(root, depth=0):...:对于 root.children 中的孩子:...:打印('' * 深度 + '%r' % 子级)...:print_tree(孩子，深度+ 1)...:在 [25] 中:print_tree(root)<节点A><节点B><节点C><节点D><节点E><节点F><节点G><节点H>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
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.
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.
Thank you.
--- EDITED ---
Here's what I wrote:
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)
And it gives:
<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)
...:
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']))
...:
Now, to check out our tree:
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]: []
Using your handy print_tree function:
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屋！
