@TOC
# Tree ADT
tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch),'branches must be a tree'
    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)

tree函数用于构造，label函数和branches函数用于选择，is_leaf和is_tree函数用于辅助

例子

fib_tree

1
2
3
4
5
6
7
def fib_tree(n):
    if n == 0 or n == 1:
        return tree(n)
    else:
        left, right = fbi_tree(n-1), fbi_tree(n-2)
        fib_n = label(left)+label(right)
        return tree(fib_n,left+right)

可见，基本情况是n == 0 or n ==1
树递归的思想是从上到下，一旦到达基本情况变返回递归结果
这段函数从树顶端递归到0 or 1的情况，然后根据0和1的结果，逐层向上计算树节点的值

count_leaf

1
2
3
4
5
6
def count_leaves(tree):
      if is_leaf(tree):
          return 1
      else:
          branch_counts = [count_leaves(b) for b in branches(tree)]
          return sum(branch_counts)

不断递归检查树枝是否为叶子，一旦是，便返回1并存储在数列中。最后用sum求树叶数

leaves

1
2
3
4
5
def leaves(tree):
	if is_leaf(tree):
		return [label(tree)]
	else:
		return sum([leaves(b) for b in branches(tree)],[])

分离树叶，不断递归检查树枝是否为树叶，若是，以数列形式存储在[ ]中，最后用sum消去一层[ ]
#为什么要用sum(, [])？
因为当该分支只存在树叶时，leavers(b) for b in branches(tree)是以数列形式出现的，而若该分支同时存在树叶和树枝时，则返回单单数字(int).

increment_leaf:

1
2
3
4
5
6
7
8
9
10
def increment_leaf(t):
    if is_leaf(t):
        return tree(label(t)+1)
    else:
        return tree(label(t),[increment_leaves(b) for b in branches(t)])

#OR
def increment(t):
    return tree(label(t)+1,[increment(b) for b in branches(t)])

上面的increment只增加leaf
下面的increment增加所有节点

1
2
3
4
def print_tree(t,indent = 0):
    print(' '*indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent+1)
1
2
3
4
5
6
7
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)

count_paths

1
2
3
4
5
6
def count_paths(t, total):
    if label(t) == total:
        found = 1
    else:
        found = 0
    return found + sum([count_paths(b,total-label(t)) for b in branches(t)])

重点在于返回的count_paths(b,total-label(t)中的total-label(t)
在递归过程中，total-label(t)不断更新到达下一分支时，满足条件的值。

输出结果

图示

练习

berry_finder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.
    >>> t = tree(1, [tree('berry',[tree('not berry')])])
    >>> berry_finder(t)
    True
    """
    "*** YOUR CODE HERE ***"
    if label(t) == 'berry':
        return True
    for branch in branches(t):
        if berry_finder(branch):
            return True
    return False

replace_loki_at_leaf

1
2
3
4
5
6
7
8
def replace_loki_at_leaf(t, lokis_replacement):
    """Returns a new tree where every leaf value equal to "loki" has
    been replaced with lokis_replacement."""
    if label(t) == 'loki'and is_leaf(t):
        return tree(lokis_replacement, [replace_loki_at_leaf(branch,lokis_replacement) for branch in branches(t)])
    else:
        return tree(label(t),[replace_loki_at_leaf(branch,lokis_replacement) for branch in branches(t)])

Height

1
2
3
4
5
6
7
8
9
10
11
12
# Q5: Height
def height(t):
    """Return the height of a tree.
    >>> t = tree(3, [tree(5, [tree(1)]), tree(2)])
    >>> height(t)
    2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 0
    else:
        return 1+max([height(branch) for branch in branches(t)])

find_path

1
2
3
4
5
6
7
8
9
10
11
12
13
def find_path(t, x):
    """
    >>> t = tree(2, [tree(7, [tree(3), tree(6, [tree(5), tree(11)])] ), tree(15)])
    >>> find_path(t, 5)
    [2, 7, 6, 5]
    >>> find_path(t, 10)  # returns None
    """
    if label(t) == x:
        return [label(t)]
    for branch in branches(t):
        path = find_path(branch, x)
        if path:
            return [label(t)] + path

sprout_leaves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sprout_leaves(t, leaves):
    """Sprout new leaves containing the data in leaves at each leaf in
    the original tree t and return the resulting tree.
    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5
    """
    if is_leaf(t):
        return tree(label(t),[tree(leaf) for leaf in leaves])
    return tree(label(t),[sprout_leaves(branch,leaves) for branch in branches(t)])

总结

我们可以发现，完成这些例子和练习的核心思想有：

  1. 重构tree，且将branches部分用递归方法不断更新为我们需要的树枝。
  2. 利用 for语句和branches选择函数对函数进行递归。
  3. 而递归的关键就在于我们对基本情况的定义和对tree ADT的理解应用。