In "Data Structures and Algorithms in Python" of Michael T. Goodrich, page 334, I've found the implementation of preorder traversal a little bit confusing.
def _subtree_preorder(self, p):
"""Generate a preorder iteration of positions in subtree rooted at p."""
yield p # visit p before its subtrees
for c in self.children(p): # for each child c
for other in self._subtree_preorder(c): # do preorder of c’s subtree
yield other # yielding each to our caller
I wonder why if there are any differences between the above implementation with:
def _subtree_preorder(self, p):
yield p
for c in self.children(p):
yield from self._subtree_preorder(c)
The author just explained:
"because we are relying on generators rather than traditional functions, the recursion has a slightly different form. In order to yield all positions within the subtree of child
c, we loop over the positions yielded by the recursive callself._subtree_preorder(c), and reyield each position in the outer context. Note that ifpis a leaf, the for loop overself.children(p)is trivial (this is the base case for our recursion)."
I don't understand what he meant, can you help me?
Thanks