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>