1
2
3
4
4
4
❤
5
❤
5
❤
5
❤
5
6
7
7
tree(label, branches)
label(tree)
branches(tree)
is_leaf(tree)
t = tree(3, [
tree(1),
tree(2, [
tree(1),
tree(1)
])])
branches
label
tree tree
tree
label(t) # 3
is_leaf(branches(t)[0]) # True
8
t = tree(3, [
tree(1),
tree(2, [
tree(1),
tree(1)
])])
[3, [1], [2, [1], [1]]] def tree(label, branches=[]):
return [label] + list(branches)
def label(tree): return tree[0]
def branches(tree): return tree[1:]
def is_leaf(tree):
return len(branches(tree)) == 0
9
10
def count_leaves(t):
“””Returns the number of leaf nodes in T.””” if
else:
11
def count_leaves(t):
“””Returns the number of leaf nodes in T.””” if is_leaf(t):
else:
11
def count_leaves(t):
“””Returns the number of leaf nodes in T.””” if is_leaf(t):
return 1 else:
11
def count_leaves(t):
“””Returns the number of leaf nodes in T.””” if is_leaf(t):
return 1 else:
leaves_under = 0
for b in branches(t):
leaves_under += count_leaves(b) return leaves_under
11
sum()
sum([1, 1, 1, 1]) # 4
12
sum()
sum([1, 1, 1, 1]) # 4
def count_leaves(t):
“””Returns the number of leaf nodes in T.””” if is_leaf(t):
return 1 else:
branch_counts = [count_leaves(b) for b in branches(t)] return sum(branch_counts)
12
13
def double(t):
“””Returns a tree identical to T, but with all labe if
else:
14
l
s
def double(t):
“””Returns a tree identical to T, but with all labe if is_leaf(t):
else:
14
l
s
def double(t):
“””Returns a tree identical to T, but with all labe if is_leaf(t):
return tree(label(t) * 2) else:
14
l
s
def double(t):
“””Returns a tree identical to T, but with all labe if is_leaf(t):
return tree(label(t) * 2) else:
return tree(label(t) * 2,
[double(b) for b in branches(t)])
14
l
s
def double(t):
“””Returns the number of leaf nodes in T.””” return tree(label(t) * 2,
[double(b) for b in branches(t)])
15
def print_tree(t, indent=0):
“””Prints the labels of T with depth-based indent.
>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])]) >>> print(t)
3
1 2
1
1 “””
16
def print_tree(t, indent=0):
“””Prints the labels of T with depth-based indent.
>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])]) >>> print(t)
3
1 2
1
1 “””
print(indent * ” ” + label(t)) for b in branches(t):
print_tree(t, indent + 2)
17
def leaves(t):
“””Return a list containing the leaf labels of T.
>>> t = tree(20, [tree(12, [tree(9, [tree(7), tree(2)]), tree(3)] >>> leaves(t)
[7, 2, 3, 4, 4]
“””
sum([ [1], [2, 3], [4] ], []) # [1, 2, 3, 4]
sum([ [1] ], []) # [1]
sum([ [[1]], [2] ], []) # [[1], 2]
18
),
def leaves(t):
“””Return a list containing the leaf labels of T.
>>> t = tree(20, [tree(12, [tree(9, [tree(7), tree(2)]), tree(3)] >>> leaves(t)
[7, 2, 3, 4, 4]
“””
if is_leaf(t):
return [label(t)] else:
leaf_labels = [leaves(b) for b in branches(t)] return sum(leaf_labels, [])
19
),
def count_paths(t, total):
“””Return the number of paths from the root to any node in t for which the labels along the path sum to total.
>>> t = tree(3, [tree(-1), tree(1, [tree(2, [tree(1)]), tree(3)]), tree(1, [tre
>>> count_paths(t, 3)
2
>>> count_paths(t, 4)
2
>>> count_paths(t, 5)
0
>>> count_paths(t, 6)
1
>>> count_paths(t, 7)
2
“””
20
e(
–
def count_paths(t, total):
“””Return the number of paths from the root to any node in t for which the labels along the path sum to total.
>>> t = tree(3, [tree(-1), tree(1, [tree(2, [tree(1)]), tree(3)]), tree(1, [tre
>>> count_paths(t, 3)
2
>>> count_paths(t, 4)
2
>>> count_paths(t, 5) 0
>>> count_paths(t, 6) 1
>>> count_paths(t, 7) 2
“””
if label(t) == total:
found = 1 else:
found = 0
return found + sum([count_paths(b, total – label(t)) for b in branches(t)])
21
e(
–
1 2 3″a” “b” “c” [..,..]
tree() branches() label()
is_leaf()
double(t) count_leaves(t)
22
23
24
25
26
27
28