伯克利 CS61A 课堂笔记 10 —

伯克利 CS61A 课堂笔记 10 —— Trees

本系列为加州伯克利大学著名 Python 基础课程 CS61A 的课堂笔记整理，全英文内容，文末附词汇解释。

01 Trees 树

Ⅰ Tree Abstraction

Ⅱ Implementing the Tree Abstraction

02 Tree Processing 建树过程

Ⅰ Fibonacci tree

Ⅱ Tree Processing uses recursion

Ⅲ Creating Trees

03 Example: Printing Trees

04 Example: Summing Paths

05 Example: Counting Paths

附：词汇解释

01 Trees 树

Ⅰ Tree Abstraction

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.

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.

Ⅱ Implementing the Tree Abstraction

>>> tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
[3, [1], [2, [1], [1]]]

#Trees

def tree(label, branches=[]):
    #Verifies the tree definition
    for branch in branches:
        assert is_tree(branch)
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

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

def is_tree(tree):
    #Verifies the tree definition
    if type(tree) != list or len(tree) < 1:
        return false
    for branch in branches(tree):
        if not is_tree(branch):
            return false
    return true

>>> tree(1)
[1]
>>> is_leaf(tree(1))
true

>>> t = tree(1, [tree(5, [tree(7)]), tree(6)])
>>> t
[1, [5, [7]], [6]]
>>> label(t)
1
>>> branches(t)
[[5, [7]], [6]]
>>> branches(t)[0]
[5, [7]]
>>> is_tree(branches(t)[0])
true
>>> label(branches(t)[0])
5

02 Tree Processing 建树过程

Ⅰ Fibonacci tree

def fib_tree(n):
    if n <= 1:
        return tree(n)
    else:
        left, right = fib_tree(n-2), fib_tree(n-1)
        return tree(label(left)+label(right), [left, right])

>>> fib_tree(0)
[0]
>>> fib_tree(1)
[1]
>>> fib_tree(2)
[1, [0], [1]]
>>> fib_tree(4)
[3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]
>>> label(fib_tree(4))
3

Ⅱ Tree Processing uses recursion

Processing a leaf is often the base of a tree processing function.

The recursive case typically makes a recursive call on each branch, then aggregates the results.

def count_leaves(t):
    """Count the leaves of a tree."""
    if is_leaf(t):
        return 1
    else:
        #寻找分支的叶子
        return sum([count_leaves(b) for b in branches(t)])

>>> count_leaves(fib_tree(4))
5

>>> count_leaves(fib_tree(10))
89

Implement leaves, which returns a list of the leaf 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(4))
    [0, 1, 1, 0, 1]
    """
    
    if is_leaf(tree):
        return [label(tree)]
    else:
        #寻找分支的叶子
        return sum([leaves(b) for b in branches(tree)], [])

Ⅲ 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:
        return tree(label(t), [increment_leaves(b) for b in branches(t)])

def increment(t):
    """Return a tree like t but with all labels incremented."""
    return tree(label(t) + 1, [increment_leaves(b) for b in branches(t)])

03 Example: Printing Trees

#原始版
def print_tree(t):
    print(label(t))
    for b in branches(t):
        print_tree(b)

>>> print_tree(fib_tree(4))
3
1
0
1
2
1
1
0
1

#升级版
def print_tree(t, indent=0){
    print(' ' * indent + str(label(t)))
    for b in branches(t):
    	print_tree(b, indent + 1)
}

>>> print_tree(fib_tree(4))
3
 1
  0
  1
 2
  1
  1
   0
   1

04 Example: Summing Paths

def fact(n):
    "Return n * (n-1) * ... * 1"
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

def fact_times(n, k):
    "Return k * n * (n-1) * ... * 1"
    if n == 0:
        return k
    else:
        return fact_times(n - 1, k * n)

def fact_plus(n):
    return fact_times(n, 1)

>>> fact_plus(4)
24

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):
    so_far = so_far + label(t)
    if is_leaf(t):
        print(so_far)
    else:
        for b in branches(t):
            print_sums(b, so_far)

>>> print_sums(numbers, 0)
7
14
>>> print_sums(haste, '')
has
hat
he

05 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)
    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))