CS61A: Lecture 13

Data Abstraction

• Not inherently implemented within the python interpreter. A set of behaviors defined by the programmer.
  • We may refer to the data and the parts without any worry about how they are implemented.
• We do this because the code becomes easier to revist and revise. We many edit features at each level of abstraction without any contradictions or mistakes to other prtions of the program.
• Ex: Line

def line(slope, intercept):
    return lambda x: slope * x + intercept

def slope(f):
    return f(1)-f(0)

def y_intercept(f):
    return f(0)

#### Abstraction barrier
#### We do not directly refer to the line type, or how it is implemented.
def parallel(f, g):
    return slope(f) == slope(g)

def increasing(f):
    return slope(f) > 0

f = line(3,5)
g = line(3, 10)
print("slope:", slope(f))
print("line value at 2:", 2)
print("are parallel?", parallel(f, g))
print("are increasing?", increasing(f))

slope: 3
line value at 2: 2
are parallel? True
are increasing? True

Trees

Tree Abstraction

• A tree is a hierarchical abstraction to contain data.
  • A general data structure. can contain numbers, letters, etc.
  • The tree can be categorized into branches and roots.
    • Every branch has a root.
    • Every branch is a tree.
    • A tree with no branches is called a leaf
    • A tree starts at the root
  • A tree can also be described relatively
    • Every location in a tree is called a node
    • Each node as a lable that can be any value
    • One node can be the parent/child of another
    • The top node is the root node
  • A path is a collection of nodes that enable us to travel from one root node to another child node.

Using the Tree Abstraction

• For a tree t, you can only:
  • Get the label for the root of the tree: label(t)
  • Get the list of branches for the tree: branches(t)
  • Get the branch at an index i, which is a tree: branches(t)[i]
  • Determine whether the tree is a leaf: is_leaf(t)
  • Treat t as a value: return t, f(t), [t], s=t

from tree import *
tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
u = tree(3, [tree(4, [tree(5)]), tree(7)])
print(label(branches(u)[1]))
print(label(branches(branches(u)[0]))[0])

7
5

Tree Processing Uses Recursion

• We always use recursion to interpret or traverse a tree.

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)

Writing Recursive Functions

• What recursive calls will you make?
• What type of values do they return?
• What do the possible return values mean?
• How can you use those return values to complete your implementation?

def largest_label(t):
    """Return the largest label in tree t."""
    if is_leaf(t):
        return label(t)
    else:
        return max([largest_label(b) for b in branches(t)] + [label(t)])
    
t1 = tree(3, [tree(4, [tree(5)]), tree(7), tree(1)])
largest_label(t1)

7

def above_root(t):
    """print all the lavels of t that are larger tan the root label."""
    def process(u):
        if label(u) > label(t):
            print(label(u))
        for b in branches(u):
            process(b)
    process(t)

above_root(t1)

4
5
7