def tree(label, branches=[]):
for b in branches:
assert is_tree(b), 'branches must be trees'
return [label] + list(branches)
def label(tree):
return tree[0]
def branches(tree):
return tree[1:]
def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for b in branches(tree):
if not is_tree(b):
return False
return True
def is_leaf(tree):
return not branches(tree)
### +++ === ABSTRACTION BARRIER === +++ ###
def print_tree(t, indent=0):
""" Prints levels of tree `t` indented by a space.
>>> print_tree(tree(1))
1
>>> t = tree(3, [tree(1),
... tree(2, [tree(1),
... tree(1)])])
>>> print_tree(t)
3
1
2
1
1
"""
print(' ' * indent + str(label(t)))
for b in branches(t):
print_tree(b, indent + 1)
# First working solution
def count_nodes(t):
""" Counts the number of nodes in tree `t`
>>> count_nodes(tree(1))
1
>>> t = tree(8, [tree(4, [tree(2),
... tree(3)]),
... tree(3, [tree(1),
... tree(1, [tree(1),
... tree(1)])])])
>>> count_nodes(t)
9
"""
if is_leaf(t):
return 1
total = 1
for b in branches(t):
total += count_nodes(b)
return total
# Taking out base case solution
def count_nodes(t):
total = 1
for b in branches(t):
total += count_nodes(b)
return total
# Simplified solution
def count_nodes(t):
return 1 + sum([count_nodes(b) for b in branches(t)])
# First working solution
def list_leaves(t):
""" Returns a list of the labels of the leaves from
tree `t`.
>>> list_leaves(tree(1))
[1]
>>> company_tree = tree('D', [tree('B', [tree('A'),
... tree('C')]),
... tree('F', [tree('E'),
... tree('H', [tree('G'),
... tree('I')])])])
>>> list_leaves(company_tree)
['A', 'C', 'E', 'G', 'I']
"""
if is_leaf(t):
return [label(t)]
leaves = []
for b in branches(t):
leaves += list_leaves(b)
return leaves
# Simplified solution
def list_leaves(t):
if is_leaf(t):
return [label(t)]
return sum([list_leaves(b) for b in branches(t)], [])
# First working solution
def square_tree(t):
""" Returns a new tree with the same structure as `t`
with every label squared.
>>> print_tree(square_tree(tree(2)))
4
>>> t = tree(3, [tree(2),
... tree(2, [tree(1),
... tree(1)])])
>>> print_tree(square_tree(t))
9
4
4
1
1
"""
if is_leaf(t):
return tree(label(t) ** 2)
squared_branches = []
for b in branches(t):
squared_branches += [square_tree(b)]
return tree(label(t) ** 2, squared_branches)
# Simplified solution
def square_tree(t):
return tree(label(t) ** 2, [square_tree(b) for b in branches(t)])
def fib_tree(n):
""" Returns a fib tree with root label fib(n) and its branches
are also fib trees.
>>> print_tree(fib_tree(0))
0
>>> print_tree(fib_tree(1))
1
>>> print_tree(fib_tree(4))
3
1
0
1
2
1
1
0
1
"""
if n == 0 or n == 1:
return tree(n)
left, right = fib_tree(n - 2), fib_tree(n - 1)
fib_n = label(left) + label(right)
return tree(fib_n, [left, right])