Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #84074
| References | <CAG=hEY1L-39EmuWpdEh_n-BNfs=qG9nL=MrMT0ar72yGBrkoUA@mail.gmail.com> <mailman.17884.1421734095.18130.python-list@python.org> <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd@googlegroups.com> |
|---|---|
| From | Ian Kelly <ian.g.kelly@gmail.com> |
| Date | 2015-01-20 10:19 -0700 |
| Subject | Re: Trees |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.17892.1421774424.18130.python-list@python.org> (permalink) |
On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody <rustompmody@gmail.com> 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
> =====================
:-)
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 01:08 -0500
Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 11:45 +0200
Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 10:14 -0800
Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 22:26 +0200
Re: Trees Stephen Hansen <me+python@ixokai.io> - 2015-01-20 23:56 -0800
Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-21 10:35 +0200
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 04:09 -0800
Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-21 23:35 +1100
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 07:24 -0800
Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 06:55 -0600
Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 00:01 +1100
Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 08:26 -0600
Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 01:31 +1100
Re: Trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-22 01:47 +1100
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 09:15 -0700
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 10:27 -0700
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:33 -0800
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:51 -0800
Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 16:15 +0200
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 06:35 -0800
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-20 10:19 -0700
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:15 -0800
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:35 -0800
Re: Trees Mario <marfig@gmail.com> - 2015-01-20 22:47 +0100
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 17:23 -0800
Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 17:49 -0800
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 18:03 -0800
Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 14:27 -0800
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:17 -0800
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 15:54 -0700
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:20 -0800
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-22 00:01 -0700
Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 23:56 -0700
Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 23:16 -0800
Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-22 08:54 -0800
Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 21:19 -0500
Re: Trees Mario Figueiredo <marfig@gmail.com> - 2015-01-21 14:05 +0000
csiph-web