How To Build A Nested Tree Structure From A List Of Adjacencies?
Solution 1:
You mention two issues in this piece of code:
tree = Tree(k, d[k]) #1st issue: should input a Tree() as 2nd parameterfor child in d[k]:
build_tree(child) #2nd issue: should populate tree, not iterate recursively over children keys
You can solve them by essentially moving the for
loop into the second argument, in the form of list comprehension and splashing that list so they become arguments. And then make sure your recursive function returns the created tree:
return Tree(k,
*[build_tree(child) for child in d[k]]
)
More ideas
Unrelated to your question, but here are some more ideas you could use.
It would be advisable to make your code a function to which you can pass
A
as argument, so that also the dictionary's scope is just local to that function and does not litter the global scope.As this feature is strongly related to the
Tree
class, it would be nice to define it as a static or class method within the class.When you have the (child, parent) tuples for the tree, then these implicitly define which node is the root, so you could omit passing the literal 66 to your function. That function should be able to find out which is the root by itself. While creating the dictionary it can also collect which nodes have a parent. The root is then the node that is not in that collection.
So taking all that together you would have this:
from collections import defaultdict
classTree:
def__init__(self, node, *children):
self.node = node
self.children = children if children else []
def__str__(self):
return"%s" % (self.node)
def__repr__(self):
return"%s" % (self.node)
def__getitem__(self, k):
ifisinstance(k, int) orisinstance(k, slice):
return self.children[k]
ifisinstance(k, str):
for child in self.children:
if child.node == k:
return child
def__iter__(self):
return self.children.__iter__()
def__len__(self):
returnlen(self.children)
@classmethoddeffrom_pairs(Cls, pairs):
# Turn pairs into nested dictionary
d = defaultdict(list)
children = set()
for child, parent in pairs:
d[parent].append(child)
# collect nodes that have a parent
children.add(child)
# Find root: it does not have a parent
root = next(parent for parent in d if parent notin children)
# Build nested Tree instances recursively from the dictionarydefsubtree(k):
return Cls(k, *[subtree(child) for child in d[k]])
return subtree(root)
# Sample run
A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66), (37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]
tree = Tree.from_pairs(A)
Solution 2:
You're close. The critical thing is to return the new node back to the parent and append it to the parent node's children list. If your parent list is fixed upon initialization, simply use a temporary list, then create the parent after visiting and creating the children.
Here's a minimal example:
from collections import defaultdict, namedtuple
def build_tree(tree, root):
if root:
return Node(root, [build_tree(tree, x) for x in tree.get(root, [])])
def print_tree(root, indent=0):
if root:
print(" " * indent + str(root.val))
for child in root.children:
print_tree(child, indent + 2)
if __name__ == "__main__":
A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66),
(37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]
Node = namedtuple("Node", "val children")
nodes = defaultdict(list)
for child, parent in A:
nodes[parent].append(child)
print_tree(build_tree(nodes, 66))
Output:
66
61
50
6
68
37
11
5
33
71
57
72
Solution 3:
Here's an opportunity to learn about reusable modules and mutual recursion. This solution in this answer solves your specific problem without any modification of the modules written in another answer. This is an important thing to point out because it shows how generic functions promote code reuse and lessen the chance for bugs to creep into your program.
First we will define functions that are specific to the shape of your (id, parent)
input structure -
# main.pydefid(node):
return node[0]
defparent(node):
return node[1]
n = (12,34)
id(n) # => 12
parent(n) # => 34
And maybe you know that the root node is 66
, but that's hard for our program to infer and easy for us to define. Let's explicitly include (66, None)
in your input data, where parent=None
signifies a root node -
A = \
[ (61, 66), (50, 61), (68, 61), (33, 61)
, (57, 66), (72, 66), (37, 68), (71, 33)
, (6, 50), (11, 37), (5, 37), (66, None) # don't forget root node, 66
]
Now we can use the tree
module to construct our tree with ease -
# main.pyfrom tree import tree
defid#...defparent#...
A = [ ... ]
B = tree \
( A # list of nodes
, parent # foreign key
, lambda node, children: # node reconstructor
(id(node), children(id(node))) # primary key
)
print(B)
# [(66, [(61, [(50, [(6, [])]), (68, [(37, [(11, []), (5, [])])]), (33, [(71, [])])]), (57, []), (72, [])])]
Notice how tree
does not concern itself with the shape of your input; any node structure can be used. The tree
function is flexible, and allows us to construct tree nodes in a shape completely different from the input nodes -
# main.pyfrom tree import tree
from json import dumps
defid#...defparent#...
A = [ ... ]
C = tree \
( A
, parent
, lambda node, children:
dict([("id", id(node)), ("children", children(id(node)))])
)
print(dumps(C))
[ { "id": 66
, "children":
[ { "id": 61
, "children":
[ { "id": 50
, "children":
[ { "id": 6, "children": [] }
]
}
, { "id": 68
, "children":
[ { "id": 37
, "children":
[ { "id": 11, "children": [] }
, { "id": 5, "children": [] }
]
}
]
}
, { "id": 33
, "children":
[ { "id": 71, "children": [] }
]
}
]
}
, { "id": 57, "children": [] }
, { "id": 72, "children": [] }
]
}
]
Now we can look at the implementation of tree
. Notice how tree
makes no assumptions about the shape of the input nodes -
# tree.pyfrom index import index, get
defempty():
return []
deftree (all, indexer, maker, root = None):
mem = index(all, indexer)
defmany(all):
returnlist(map(one, all))
defone(single):
return maker(single, lambda r: many(get(mem, r, empty())))
return many(get(mem, root))
Our implementation of tree
depends on another module, index
. Grouping data structures, like index, along with functions that operate on those data structures is a good way to draw boundaries between modules. No assumptions about input shape made here either -
# index.pyfrom functools import reduce
defempty():
return {}
defupdate(t, k, f):
if k in t:
return { **t, k: f(get(t, k)) }
else:
return { **t, k: f() }
defget(t, k, default = None):
if k in t:
return t[k]
else:
return default
defappend(t, k, v):
return update(t, k, lambda r = []: [ *r, v ])
defindex(ls, indexer):
return reduce \
( lambda t, v: append(t, indexer(v), v)
, ls
, empty()
)
Verify our results by running it in your browser: run this program on repl.it
Modules ported to Python. Original program written in JavaScript.
Post a Comment for "How To Build A Nested Tree Structure From A List Of Adjacencies?"