伯克利 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]]]

#Treesdef tree(label, branches=[]):#Verifies the tree definitionfor 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 definitionif type(tree) != list or len(tree) < 1:return falsefor branch in branches(tree):if not is_tree(branch):return falsereturn 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 1else:#寻找分支的叶子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))
310121101

04 Example: Summing Paths

def fact(n):"Return n * (n-1) * ... * 1"if n == 0:return 1else:return n * fact(n - 1)def fact_times(n, k):"Return k * n * (n-1) * ... * 1"if n == 0:return kelse: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 tfor 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 = 1else:found = 0return found + sum(count_paths(b, total - label(t)) for b in branches(t))