On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody <[email protected]> wrote:
> from enum import Enum
> class TreeTag(Enum):
> I = 0 # An internal node
> L = 1 # A leaf node
> def __repr__(self): return self.name
>
> I = TreeTag.I
> L = TreeTag.L
Explicitly tagging nodes as internal or leaves is kind of ugly and
also prone to getting out of sync with the reality, which is that a
node is a leaf if it doesn't have any other nodes hanging off of it.
> def dfs(t):
> if t[0] == L:
> return [t[1]]
> else:
> return [t[1]] + dfs(t[2]) + dfs(t[3])
Over the entire tree, this will do O(n) list additions which implies
O(n) list *copies*, which is rather inefficient. This would probably
be better implemented as a recursive generator.
def dfs(t):
yield t[0]
yield from chain.from_iterable(map(dfs, islice(t, 1, None)))
> # Converting to generators is trivial
> =====================
:-)
--
https://mail.python.org/mailman/listinfo/python-list
