# Tree ADT
def tree(label, branches=[]):
“””Construct a tree with the given label value and a list of branches.”””
if change_abstraction.changed:
for branch in branches:
assert is_tree(branch), ‘branches must be trees’
return {‘label’: label, ‘branches’: list(branches)}
else:
for branch in branches:
assert is_tree(branch), ‘branches must be trees’
return [label] + list(branches)
def label(tree):
“””Return the label value of a tree.”””
if change_abstraction.changed:
return tree[‘label’]
else:
return tree[0]
def branches(tree):
“””Return the list of branches of the given tree.”””
if change_abstraction.changed:
return tree[‘branches’]
else:
return tree[1:]
def is_tree(tree):
“””Returns True if the given tree is a tree, and False otherwise.”””
if change_abstraction.changed:
if type(tree) != dict or len(tree) != 2:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
else:
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
"""Returns True if the given tree's list of branches is empty, and False
otherwise.
"""
return not branches(tree)
def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the root.
>>> print_tree(tree(1))
1
>>> print_tree(tree(1, [tree(2)]))
1
2
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
“””
print(‘ ‘ * indent + str(label(t)))
for b in branches(t):
print_tree(b, indent + 1)
def copy_tree(t):
“””Returns a copy of t. Only for testing purposes.
>>> t = tree(5)
>>> copy = copy_tree(t)
>>> t = tree(6)
>>> print_tree(copy)
5
“””
return tree(label(t), [copy_tree(b) for b in branches(t)])
————————————————————————–
class Tree:
“””
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t.label
3
>>> t.branches[0].label
2
>>> t.branches[1].is_leaf()
True
“””
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = list(branches)
def is_leaf(self):
return not self.branches
def map(self, fn):
“””
Apply a function `fn` to each node in the tree and mutate the tree.
>>> t1 = Tree(1)
>>> t1.map(lambda x: x + 2)
>>> t1.map(lambda x : x * 4)
>>> t1.label
12
>>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t2.map(lambda x: x * x)
>>> t2
Tree(9, [Tree(4, [Tree(25)]), Tree(16)])
“””
self.label = fn(self.label)
for b in self.branches:
b.map(fn)
def __contains__(self, e):
“””
Determine whether an element exists in the tree.
>>> t1 = Tree(1)
>>> 1 in t1
True
>>> 8 in t1
False
>>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> 6 in t2
False
>>> 5 in t2
True
“””
if self.label == e:
return True
for b in self.branches:
if e in b:
return True
return False
def __repr__(self):
if self.branches:
branch_str = ‘, ‘ + repr(self.branches)
else:
branch_str = ”
return ‘Tree({0}{1})’.format(self.label, branch_str)
def __str__(self):
def print_tree(t, indent=0):
tree_str = ‘ ‘ * indent + str(t.label) + “\n”
for b in t.branches:
tree_str += print_tree(b, indent + 1)
return tree_str
return print_tree(self).rstrip()
————————————————————————–
class Link:
“””A linked list.
>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.first = 5
>>> s.rest.first = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
<5 7 <8 9>>
“””
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_repr = ‘, ‘ + repr(self.rest)
else:
rest_repr = ”
return ‘Link(‘ + repr(self.first) + rest_repr + ‘)’
def __str__(self):
string = ‘<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>‘