CS61A(12): Trees

Posted on | In |

This is the lecture note of CS61A - Lecture 12.

Processing Container Values

  • sum(iterable[, start=0]) -> value
  • max(iterable[, key=func]) -> value, min(iterable[, key=func]) -> value
  • all(iterable) -> bool
  • any(iterable) -> bool
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Aggregation

>>> lst = [1, 2, 3]
>>> lst[3]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>> lst[3:]
[]

>>> sum([2, 3, 4], 5)       # ==> 5 + 2 + 3 + 4
14
# Hint: If you sum a list of lists, you get a list containing the elements of those lists.
>>> sum([[2, 3], [4]], [])  # ==> [] + [2, 3] + [4]
[2, 3, 4]
>>> sum([ [[1]], [2] ], []) # ==> [] + [[1]] + [2]
[[1], 2]

>>> sum([[2, 3], [4]])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'

>>> sum({3:9, 5:25})
8

>>> max(0, 1, 2, 3, 4)
4
>>> max(range(10), key=lambda x: 7 - (x-2)*(x-4))
3 

>>> all([x < 5 for x in range(5)])
True

>>> perfect_square = lambda x: x == round(x ** 0.5) ** 2
>>> any([perfect_square(x) for x in range(50, 60)])     # Try ,65)
False

Trees

Tree is an important data abstraction for representing hierarchical relationship.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Trees: recursive implementation

def tree(label, branches=[]):
    # verifies the tree def
    for branch in branches: 
        assert is_tree(branch), 'branches must be trees'
    # list(branches): create a list from a sequence branches
    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 branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

"""
>>> t = tree(1, [tree(5, [tree(7)]), tree(6)])
[1, [5, [7]], [6]]
"""

Tree Processing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
### +++ === ABSTRACTION BARRIER === +++ ###

# construct fibonacci tree
def fib_tree(n):
    """Construct a Fibonacci tree.

    >>> fib_tree(1)
    [1]
    >>> fib_tree(3)
    [2, [1], [1, [0], [1]]]
    >>> fib_tree(5)
    [5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]
    """
    if n == 0 or n == 1:
        return tree(n)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        fib_n = label(left) + label(right)
        return tree(fib_n, [left, right])


def count_leaves(t):
    """The number of leaves in tree.

    >>> count_leaves(fib_tree(5))
    8
    """
    if is_leaf(t):
        return 1
    else:
        return sum([count_leaves(b) for b in branches(t)])


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)]
    else:
        return sum([leaves(b) for b in branches(tree)], [])


def increment_leaves(t):
    """Return a tree like t but with leaf labels incremented.
    
    >>> print_tree(increment_leaves(fib_tree(4)))
    3
      1
        1
        2
      2
        2
        1
          1
          2
    """
    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.
    
    >>> print_tree(increment(fib_tree(4)))
    4
      2
        1
        2
      3
        2
        2
          1
          2
    """
    return tree(label(t) + 1, [increment(b) for b in branches(t)])

One more example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def print_tree(t, indent=0):
    """Print a representation of this tree in which each label is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(fib_tree(4))
    3
      1
        0
        1
      2
        1
        1
          0
          1
    """
    print(' ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

Example 1: Summing Paths

First, let's see an example of tail recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Order

def fact(n):
    """Return n * n-1 * ... * 1.

    >>> fact(4)
    24
    """
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

#  非尾递归: 此函数还有后续，所以必须保存本身的环境以供处理返回值。


def fact_tail(n):
    """Return n * n-1 * ... * 1.

    >>> fact_tail(4)
    24
    """
    return fact_times(n, 1)

def fact_times(n, k):
    """Return k * n * n-1 * ... * 1.

    >>> fact_times(4, 3)
    72
    """
    if n == 0:
        return k
    else:
        return fact_times(n - 1, k * n)
        
# 尾递归: 进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。
# 尾递归是一种编程技巧。

"""
ordinary recursion: 
we need call stack to record; if too many recursive calls, sometimes stack overflow occurs.

tail recursion: 
in tail recursion, the recursive call is the last thing logically, 
and there is nothing left in the current function. 
And the compiler will optimize tail recursion. 
(we don't need stack frame anymore, and tail recursion can be optimized as ordinary loop)
"""

Then use this strategy to solve print_sums question.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from tree import * 

numbers = tree(3, [tree(4), tree(5, [tree(6)])])
haste = tree('h', [tree('a', [tree('s'), tree('t')]), tree('e')])

def print_sums(t, so_far):
    """Print the sum of labels along the path from the root to each leaf.

    >>> print_sums(numbers, 0)
    7
    14
    >>> print_sums(haste, '')
    has
    hat
    he
    """
    so_far = so_far + label(t)
    if is_leaf(t):
        print(so_far)
    else:
        for branch in branches(t):
            print_sums(branch, so_far)

Example 2: Counting Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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)
    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)])