Trees
Announcements
Hog Contest Winners
Strategy contest: https://hog-contest.cs61a.org/
3-way tie for first: , , &
After bug fix: (1) , (2) , (3) Jiayin Lin &
Dice contest: https://dice.cs61a.org/
(1) & (2) & (3)
3
Box-and-Pointer Notation
The Closure Property of Data Types
•A method for combining data values satisfies the closure property if: The result of combination can itself be combined using the same method
•Closure is powerful because it permits us to create hierarchical structures
•Hierarchical structures are made up of parts, which themselves are made up of parts, and so on
Lists can contain lists as elements (in addition to anything else)
5
Box-and-Pointer Notation in Environment Diagrams
Lists are represented as a row of index-labeled adjacent boxes, one per element
Each box either contains a primitive value or points to a compound value
6
Box-and-Pointer Notation in Environment Diagrams
Lists are represented as a row of index-labeled adjacent boxes, one per element
Each box either contains a primitive value or points to a compound value
pythontutor.com/composingprograms.html#code=pair%20%3D%20[1,%202]%0A%0Anested_list%20%3D%20[[1,%202],%20[],%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20[[3,%20False,%20None], %0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20[4,%20lambda%3A%205]]]&mode=display&origin=composingprograms.js&cumulative=true&py=3&rawInputLstJSON=[]&curInstr=4
7
Slicing
(Demo)
Slicing Creates
9
pythontutor.com/composingprograms.html#code=digits%20%3D%20[1,%208,%202,%208]%0Astart%20%3D%20digits[%3A1]%0Amiddle%20%3D%20digits[1%3A3]%0Aend%20%3D%20digits[2%3A]%0Afull%20%3D%20digits[%3A]&cumulative%3Dtrue&curInstr%3D5&mode=display&origin=composingprograms.js&py=3&rawInputLstJSON=[]
Processing Container Values
Sequence Aggregation
Several built-in functions take iterable arguments and aggregate them into a value
• sum(iterable[, start]) -> value
Return the sum of a ‘start’ value (default: 0) plus an iterable of numbers.
• max(iterable[, key=func]) -> value max(a, b, c, …[, key=func]) -> value
With a single iterable argument, return its largest item.
With two or more arguments, return the largest argument.
• all(iterable) -> bool
Return True if bool(x) is True for all values x in the iterable.
If the iterable is empty, return True.
11
Trees
Tree Abstraction
Root of the whole tree or Root Node Root label 3
Nodes Labels
Root of a branch
Branch
(also a tree)
12 0111
Recursive description (wooden trees):
A tree has a root label and a list of branches Each branch is a tree
A tree with zero branches is called a leaf
A tree starts at the root
Relative description (family trees):
Each location in a tree is called a node Each node has a label that can be any value One node can be the parent/child of another The top node is the root node
Leaf
(also a tree) Path
01
People often refer to labels by their locations: “each parent is the sum of its children”
13
Implementing the Tree Abstraction
def tree(label, branches=[]):
return [label] + branches
def label(tree):
return tree[0]
def branches(tree):
return tree[1:]
3
12 11
>>> tree(3, [tree(1),
… tree(2, [tree(1),
… tree(1)])])
[3, [1], [2, [1], [1]]]
• A tree has a root label and a list of branches
• Each branch is a tree
14
Implementing the Tree Abstraction
def tree(label, branches=[]):
for branch in branches:
assert is_tree(branch)
return [label] + list(branches)
def label(tree):
return tree[0]
def branches(tree):
return tree[1:]
3
12 11
>>> tree(3, [tree(1),
… tree(2, [tree(1),
… tree(1)])])
[3, [1], [2, [1], [1]]]
Verifies the
tree definition
Creates a list
from a sequence
of branches
Verifies that
tree is bound
to a list
• A tree has a root label and a list of branches
• Each branch is a tree
def is_tree(tree):
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):
return not branches(tree)
(Demo)
15
Tree Processing
(Demo)
Tree Processing Uses Recursion
Processing a leaf is often the base case of a tree processing function
The recursive case typically makes a recursive call on each branch, then aggregates
def count_leaves(t):
"""Count the leaves of a tree."""
if is_leaf(t):
return 1
else:
branch_counts = [count_leaves(b) for b in branches(t)]
return sum(branch_counts)
(Demo)
17
Discussion Question
Implement leaves, which returns a list of the leaf labels of a tree
Hint: If you sum a list of lists, you get a list containing the elements of those lists
>>> sum([ [1], [2, 3], [4] ], []) [1, 2,3,4]
>>> sum([ [1] ], [])
[1]
>>> sum([ [[1]], [2] ], [])
[[1], 2]
def leaves(tree):
“””Return a list containing the leaf labels of tree.
>>> leaves(fib_tree(5))
[1, 0, 1, 0, 1, 1, 0, 1]
“””
if is_leaf(tree):
return [label(tree)]
branches(tree)
leaves(tree)
[branches(b) for b in branches(tree)]
[leaves(b) for b in branches(tree)]
[b for b in branches(tree)]
[s for s in leaves(tree)]
[branches(s) for s in leaves(tree)]
[leaves(s) for s in leaves(tree)]
else:
return sum(______________________________, [])
List of leaf labels for each branch
18
Creating Trees
A function that creates a tree from another tree is typically also recursive
def increment_leaves(t):
“””Return a tree like t but with leaf labels incremented.””” if is_leaf(t):
return tree(label(t) + 1) else:
bs = [increment_leaves(b) for b in branches(t)] return tree(label(t), bs)
def increment(t):
“””Return a tree like t but with all labels incremented.””” return tree(label(t) + 1, [increment(b) for b in branches(t)])
19
Example: Printing Trees
(Demo)
Example: Summing Paths
(Demo)
Example: Counting Paths
Count Paths that have a Total Label Sum
def count_paths(t, total):
“””Return the number of paths from the root to any node in tree 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, [tree(-1)])]) >>> count_paths(t, 3)
2
>>> count_paths(t, 4) 3
2
>>> count_paths(t, 5)
0
>>> count_paths(t, 6)
1
-1 1 1
>>> count_paths(t, 7) 223 “””
if _________________:
label(t) == total
1
-1 1
found = ________________
else:
found = 0
________________________
sum count_paths(b, total – label(t))
return found + _________([__________________________________ for b in branches(t)])