Trees

[Rustom Mody]

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]
>>>