Trees

Rustom Mody rustompmody at gmail.com
Tue Jan 20 14:33:37 CET 2015

```On Tuesday, January 20, 2015 at 11:38:27 AM UTC+5:30, Terry Reedy wrote:
> On 1/19/2015 5:06 PM, Zachary Gilmartin wrote:
> > Why aren't there trees in the python standard library?
>
> Sequences nested withing sequences can be regarded as trees, and Python
> has these.  I regard Lisp as a tree processing languages, as it must be
> to manipulate, for example, code with nested structures.

Yeah python has trees alright.

Heres' some simple tree-code

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

def dfs(t):
if t[0] == L:
return [t[1]]
else:
return [t[1]] + dfs(t[2]) + dfs(t[3])

# Converting to generators is trivial
=====================

# Example tree
# From http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html

t1 = [L, 1]
t4 = [I, 4, [L, 3],[L,5]]
t2 = [I, 2, t1, t4]
t8 = [I, 8, [L, 7], [L, 9]]

# Top level tree
t = [I, 6, t2, t8]

======================
An REPL session

>>> t
[I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]]
>>> dfs(t)
[6, 2, 1, 4, 3, 5, 8, 7, 9]
>>> t8
[I, 8, [L, 7], [L, 9]]
>>> dfs(t8)
[8, 7, 9]
>>>

```