伯克利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)) 附：词汇解释

verify 证明、definition 定义、aggregate / ˈæɡrɪɡət / 合计、hint / hɪnt / 提示、increment / ˈɪŋkrəmənt / 增长、indent / ɪnˈdent / 缩进、factorial / fækˈtɔːriəl / 阶乘