自己怎么建个免费网站,淘宝网页版怎么和卖家聊天,做一个企业网站花费,怎么做网站地图的样式本系列为加州伯克利大学著名 Python 基础课程 CS61A 的课堂笔记整理#xff0c;全英文内容#xff0c;文末附词汇解释。
目录
01 Trees 树
Ⅰ Tree Abstraction
Ⅱ Implementing the Tree Abstraction
02 Tree Processing 建树过程
Ⅰ Fibonacci tree
Ⅱ Tree Process…本系列为加州伯克利大学著名 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)
1branches(t)
[[5, [7]], [6]]branches(t)[0]
[5, [7]]is_tree(branches(t)[0])
truelabel(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, indent0){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) * ... * 1if n 0:return 1else:return n * fact(n - 1)def fact_times(n, k):Return k * n * (n-1) * ... * 1if 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
14print_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)2if label(t) total:found 1else:found 0return 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 / 阶乘
